Algoritma: Perbedaan antara revisi

 

 

 

 

 

 

== Definisi informal ==

Maka sebuah algoritma dapat berupa persamaan aljabar seperti '''y = m + n''' -- dua variabel masukan '''m''' dan '''n''' yang menghasikan keluaran '''y'''.

Tapi berbagai penulis yang mencoba mendefinisikan persamaan tersebut mengatakan bahwa kata algoritma mengandung lebih dari itu, sesuatu yang kurang lebih (untuk contoh penjumlahan):

Konsep dari ''algoritma'' juga digunakan untuk mendefinisikan notasi dari [[desidabilitas (logika)|desidabilitas]].

Notasi tersebut adalah pusat untuk menjelaskan bagaimana [[sistem formal]] berasal dari sejumlah kecil [[aksioma]] dan aturan.

Dalam [[logika]], waktu dari sebuah algoritma untuk selesai tidak dapat dihitung, karena tidak berelasi dengan dimensi fisik kita.

 

== Formalisasi ==

<blockquote>

Minsky: "Tapi kita juga menjaga, dengan Turing ... bahwa setiap prosedur yang "secara alami" disebut efektif, bisa dinyatakan oleh mesin (sederhana).

<ref name="Minsky 1967:105">

'''Minsky''' 1967:105</ref>

Biasanya, bila sebuah algoritma dihubungkan dengan pengolahan informasi, data dibaca dari sumber masukan, ditulis ke perangkat keluaran, dan/atau disimpan untuk pengolahan selanjutnya.

Data simpanan dianggap sebagai bagian dari keadaan internal dari entitas yang melakukan algoritma.

 

Untuk beberapa proses komputasi, algoritma harus ditentukan secara teliti: dijabarkan dengan cara ia bakal berlaku untuk semua kemungkinan yang dapat timbul.

Ekspresi bahasa alamiah terhadap algoritma condong lebih banyak dan rancu, dan jarang digunakan untuk algoritma yang kompleks dan teknis.

Pseudokode, diagram alur, bagan drakon, dan tabel kontrol adalah cara yang terstruktur untuk menggambarkan algoritma yang mencegah banyaknya kerancuan pada pernyataan-pernyataan bahasa alamiah.

 

Ada banyak macam kemungkinan representasi dan seseorang dapat mengekspresikan sebuah program [[mesin Turing]] sebagai urutan dari tabel-tabel mesin (lihat lebih lanjut di [[mesin kondisi-terbatas]], [[tabel transisi kondisi]] dan [[tabel kontrol]]), sebagai diagram alur dan bagan drakon (lihat lebih lanjut di [[diagram kondisi]]), atau sebagai bentuk [[kode mesin]] atau [[kode assembly]] dasar yang dikenal "kumpulan lipat empat" (lihat lebih lanjut di [[mesin Turing]]).

 

Representasi dari algoritma dapat dikelompokan ke dalam tiga tingkatan dari deskripsi mesin Turing:

; '''1 Deskripsi tingkat-tinggi'''

: "... ditujukan untuk menjelaskan algoritma, menghiraukan rincian implementasi. Pada tingkat ini kita tidak perlu menyebutkan bagaimana mesin mengatur perangkat pita atau kepala pita rekam."

 

Kebanyakan algoritma ditujukan untuk diimplementasikan sebagai [[program komputer]].

 

== Algoritma komputer ==

 

 

Dalam [[sistem komputer]], sebuah algoritma pada dasarnya adalah instansi dari [[logika]] ditulis dalam [[perangkat lunak]] oleh pengembang perangkat lunak supaya efektif untuk komputer yang "ditargetkan" untuk mesin tertentu untuk menghasilkan ''keluaran'' dari ''masukan'' yang diberikan (kemungkinan nul).

 

''Program yang "elegan" (padat), program yang "baik" (cepat)'': Pernyataan dari "sederhana dan elegan" muncul secara informal dalam buku Knuth dan dalam Chaitin:

 

 

 

''Algoritma terhadap fungsi yang dapat dihitung oleh algoritma'': Untuk sebuah fungsi bisa ada beberapa algoritma.

cf gandy 1980:126, robin gandy ''church's thesis and principles for mechanisms'' appearing on pp. 123–148 in j. barwise et al. 1980 ''the kleene symposium'', north-holland publishing company.

</ref>

Sebuah "robot": "Sebuah komputer adalah sebuah robot yang melakukan setiap tugas yang dapat dijelaskan sebagai urutan dari instruksi." cf Stone 1972:3

Model primitif dari Melzak dan Lambek

<ref>

Lokasinya bisa dibedakan, penghitungnya tidak".

Lubangnya memiliki kapasitas tak terbatas, dan digerakan oleh agen yang memahami dan mampu menjalankan sejumlah instruksi" (Lambek 1961:295).

B-B-J (loc. cit.) menambahkan syarat bahwa lubang tersebut "mampu menyimpan sejumlah batu" (p. 46).

Melzak dan Lambek muncul di ''The Canadian Mathematical Bulletin'', vol. 4, no. 3, September 1961.

</ref>

Jarang seorang programer harus menulis "kode" dengan kumpulan instruksi terbatas.

<ref>

Namun, beberapa instruksi penetapan berbeda (misalnya, DECREMENT, INCREMENT, dan ZERO/CLEAR/EMPTY untuk mesin Minsky) juga dibutuhkan untuk kekomplitan-Turing;

 

''Simulasi dari sebuah algoritma: bahasa komputer (komputor)'': Knuth menganjurkan pembaca bahwa "cara terbaik untuk belajar algoritma dalah mencobanya ... langsung ambil pulpen dan kertas dan bekerja lewat contoh".

Lalu bagaimana dengan simulasi atau eksekusi yang sebenarnya?

Programmer harus menerjemahkan algoritma ke dalam bahasa yang mana simulator/komputer/komputor dapat mengeksekusi ''secara efektif''.

Jika tidak maka supaya algoritma dapat efektif ia harus menyediakan sejumlah aturan untuk mengekstrak akar kuadrat.

<ref>

</ref>

 

<ref>

{{cite book

</ref>

Bila kecepatan yang dihitung, jumlah instruksi berpengaruh.

Sebagai contohnya, subprogram dalam algoritma Euclid untuk menghitung sisa akan berjalan lebih cepat jika programmer memiliki instruksi "modulus" (sisa pembagian) bukannya dengan pengurangan (atau lebih parah: hanya "penurunan").

 

Kemeny dan Kurtz mengamati bahwa saat penggunaan GOTO tak bersyarat yang "tak disiplin" dan IF-THEN GOTO bersyarat bisa menghasilkan "[[kode spageti]]" seorang programer bisa menulis program terstruktur menggunakan instruksi tersebut;

di lain sisi "juga memungkinkan, dan tidak begitu sulit, untuk menulis sebuah program terstruktur yang buruk dalam sebuah bahasa terstruktur".

</ref>

Tausworthe menambahkan tiga [[Teorema program terstruktur|struktur kanon Bohm-Jacopini]]:

SEQUENCE, IF-THEN-ELSE, dan WHILE-DO, dengan dua lagi: DO-WHILE dan CASE.

Keuntungan dari program terstruktur adalah ia cocok dengan [[pembuktian kebenaran]] menggunakan [[induksi matematika]].

<ref>

</ref>

 

Seperti alur program dari mesin Minsky, sebuah diagram alur selalu mulai dari atas dan terus ke bawah.

Simbol utamanya hanya 4: arah panah memperlihatkan alur program, segi empat (SEQUENCE, GOTO), wajik (IF-THEN-ELSE), dan titik (OR).

 

=== Contoh Algoritma ===

 

Salah satu dari algoritma sederhana adalah menemukan bilangan terbesar dalam sebuah deretan angka (tak berurut).

Dari hal ini munculah algoritma sederhana, yang bisa dinyatakan dalam kalimat bahasa deskripsi tingkat-tinggi, sebagai:

 

{{Further2|[[Algoritma Euklid]]}}

 

 

Algoritma [[Euclid]] muncul sebagai Proposisi II dalam Book VII ("Elementary Number Theory") dari ''[[Euclid's Elements|Elements]]''.

Euclid mengajukan permasalahan: "Ambil dua angka bukan prima, untuk mencari bilangan pembagi terbesar".

Dia menentukan "Sebuah angka [merupakan] besaran yang terdiri dari unit-unit": angka penghitung, integer positif kecuali 0.

<ref>

"'Biarkan CD, mengukur BF, meninggalkan FA kurang darinya.'

==== Contoh ====

 

 

650 = 299*2 + 52

299 = 52*5 + 39

52 = 39*1 + 13

39 = 13*3 + 0

 

==== Bahasa komputer untuk algoritma Euclid ====

 

* Sebuah ''lokasi'' disimbolkan dengan huruf besar, misalnya, S, A, dll.

* Kuantitas beragam (angka) dalam sebuah lokasi ditulis dengan huruf kecil dan (biasanya) dihubungkan dengan nama lokasi. Sebagai contohnya, lokasi L pada awal bisa mengandung angka ''l'' = 3009.

==== Program yang kurang elegan (inelegan) untuk algoritma Euclid ====

 

Diambil dari Knuth 1973:2-4.

Bergantung pada kedua angka "Inelegan" bisa menghitung f.p.k dengan sedikit langkah daripada "elegan".]]

 

Deskripsi tingkat-tinggi, diperlihatkan dengan tulisan tebal, diadaptasi dari Knuth 1973:2-4:

 

ELSE

tukar isi R dan S.

{{vanchor|5|el5}} R ← S

{{vanchor|6|el6}} S ← L

Sumber pertama

<ref>{{cite web

|accessdate=May 20, 2012

}}</ref>

Apa yang terjadi bila angka ''negatif'' dimasukan?

Angka desimal?

Kesalahan yang terkenal karena eksepsi adalah kegagalan roket [[Ariane V]].

 

''Bukti dari kebenaran program menggunakan induksi matematika'': Knuth mendemonstrasikan penggunaan [[induksi matematika]] untuk versi "pengembangan" dari algoritma Euclid, dan dia mengajukan "metode umum yang digunakan untuk membuktikan validitas dari setiap algoritma."

<ref>

</ref>

Tausworthe mengajukan bahwa sebuah pengukuran dari kompleksitas dari sebuah program adalah panjang dari pembuktian kebenarannya.

Bila algoritma (biasanya) membutuhkan banyak pengulangan, ''secara rata-rata'' lebih banyak waktu yang terbuang saat melakukan tes "B = 0?" yang hanya diperlukan saat sisa sudah dihitung.

 

 

Kepadatan dari "inelegan" bisa ditingkatkan dengan menghilangkan 5 langkah.

{{Main|Analisis algoritma}}

 

Metode-metode telah dikembangkan untuk [[analisis algoritma]] untuk mendapatkan jawaban kuantitatif (estimasi);

sebagai contohnya, algoritma pengurutan di atas memerlukan waktu O(''n''), menggunakan [[notasi O besar]] dengan ''n'' sebagai panjang deret (yang akan diurut).

Biasanya [[pseudokode]] digunakan pada analisis karena merupakan representasi paling umum dan sederhana.

Namun, pada akhirnya, kebanyakan algoritma diimplementasikan di perangkat keras / lunak tertentu dan [[efisiensi algoritmik]] mereka akhirnya diuji menggunakan kode yang sebenarnya.

Meningkatkan n dari kecil ke n yang besar biasanya menunjukan ketak efisienan algoritma yang tidak berbahaya.

 

| publisher=discovermagazine.com}}</ref>

Secara umum, peningkatan kecepatan bergantung pada properti khusus dari permasalahan, yang mana sangat umum pada aplikasi praktis.

, Kyoto, January 2012.

Percepatan dengan tingkat seperti itu membolehkan perangkat komputasi yang sering menggunakan pemrosesan gambar (seperti kamera digital dan peralatan medis) menghabiskan daya yang lebih sedikit.

 

 

; Rekursi atau iterasi

 

; Logical

 

; Serial, paralel atau terdistribusi

 

; Deterministik atau non-deterministik

 

; Tepat atau perkiraan

 

; [[Algoritma quantum]]

 

== Paradigma secara rancangan ==

 

; [[Pencarian paksa]] atau pencarian mendalam

 

; Membagi dan menaklukan (''Divide and conqueror'')

 

; Pencarian dan enumerasi

 

; [[Algoritma pengacakan]]

# [[Algoritma Monte Carlo]] mengembalikan jawaban yang benar dengan probabilitas-tinggi. Misalnya, [[RP (kompleksitas)|RP]] adalah sub-klas dari algoritma ini yang berjalan dalam [[waktu polinomial]])

 

; [[Reduksi (kompleksitas)|Reduksi]]

 

=== Permasalahan optimisasi ===

 

; Pemrograman Linear

[[George B. Dantzig]] and Mukund N. Thapa. 2003. ''Linear Programming 2: Theory and Extensions''. Springer-Verlag.</ref> Permasalahan yang dapat diselesaikan dengan pemrograman linear termasuk [[permasalahan alur maksimum]] untuk grafik terarah). Jika sebuah masalah sebagai tambahan membutuhkan satu atau lebih jawaban haruslah [[integer]] maka ia diklasifikan dalam [[pemrograman integer]]. Algoritma pemrograman linear dapat menyelesaikan masalah seperti itu jika dapat dibuktikan bahwa semua batasan untuk nilai integer adalah tidak benar, yaitu solusi memenuhi batasan tersebut. Pada kasus umum, algoritma yang dikhususkan atau algoritma yang menemukan solusi perkiraan digunakan, bergantung pada kesulitan dari permasalahan.

 

: Bila sebuah masalah memperlihatkan [[substruktur optimal]], artinya solusi optimal terhadap sebuah masalah bisa direkonstruksi dari solusi optimal ke sub-masalah, dan [[submasalah tumpang-tindih]], artinya sub-masalah yang sama digunakan untuk menyelesaikan banyak instasi masalah berbeda, pendekatan tercepat disebut ''pemrograman dinamis'' menghindari penghitungan solusi yang telah dikomputasi. Sebagai contoh, [[algoritma Floyd-Warshall]], jalan terpendek ke tujuan dari sebuah vertex dalam [[grafik (matematika)|grafik]] berbobot bisa ditemukan dengan menggunakan jalan terpendek ke tujuan dari semua simpul yang berdekatan. Pemrograman dinamis dan [[memoisasi]] berpadanan. Perbedaan utama antara pemrograman dinamis dan bagi-dan-taklukan adalah submasalah kurang lebih independen dalam bagi-dan-taklukan, sementara submasalah tumpang tindik dalam pemrograman dinamis. Perbedaaan antara pemrograman dinamis dan rekursi langsung adalah dalam 'caching' atau memoisasi dari pemanggialan rekursif. Saat submasalah independen dan tidak ada pengulangan, memoisasi tidak membantu sama sekali; makanya pemrograman dinamis bukalanh solusi untuk semua permasalahan kompleks. Dengan menggunakan memoisasi atau [[tabel matematis|tabel]] dari submasalah yang telah diselesaikan, pemrograman dinamis mereduksi eksponensial dari banyak permasalahan menjadi kompleksitas polinomial.

 

 

; Metode heuristik

 

=== Berdasarkan bidang kajian ===

 

Setiap bidang sains memiliki permasalahannya sendiri dan membutuhkan algoritma yang efisien. Masalah yang berkaitan di satu bidang terkadang dipelajari bersama. Beberapa contoh yaitu [[algoritma pencarian]], [[algoritma penggabungan]], [[analisis numerik|algoritma numerik]], [[teori grafik|algoritma grafik]], [[algoritma deret]], [[geometri komputasi|algoritma komputasi geometri]], [[kombinatorial|algoritma kombinatorial]], [[algoritmas medis]], [[mesin belajar]], [[kriptografi]], algoritma [[kompresi data]] dan [[penguraian|teknik penguraian]].

 

 

=== Berdasarkan kompleksitas ===

 

 

Algoritma bisa diklasifikasikan berdasarkan jumlah waktu yang dibutuhkan untuk selesai dibandingkan dengan ukuran inputnya. Ada berbagai varietas: beberapa algoritma selesai dalam waktu linear relatif terhadap ukuran input, beberapa selesai dalam jumlah waktu yang eksponensial atau lebih buruh, dan beberapa berhenti. Sebagai tambahan, beberapa masalah bisa memiliki berbagai algoritma dengan kompleksitas yang berbeda, sementara permasalahan yang lain bisa saja tidak memiliki algoritma atau tidak diketahui algoritmanya yang efisien. Ada juga pemetaan dari beberapa algoritma terhadap permasalahan lain. Karena itu, lebih cocok untuk mengklasifikasikan permasalahan itu sendiri bukannya algoritma menjadi kelas-kelas yang sama berdasarkan kompleksitas dari kemungkinan algoritma terbaik baginya.

 

 

=== Berdasarkan tipe evaluatif ===

 

 

Untuk menjaga keseimbangan saat mengintegrasikan mesin ke dalam masyarakat, seseorang bisa mengklasifikasikan algoritma berdasarkan tipe dari evaluasi yang mereka lakukan.

 

Kata sifat "berkelanjutan" bila diterapkan pada kata "algoritma" bisa berarti:

* Sebuah algoritma dalam bentuk dari [[persamaan diferensial]] yang beroperasi secara berkelanjutan terhadap data, berjalan dalam sebuah [[komputer analog]].

<ref>{{cite book

 

== Isu legalitas ==

 

Algoritma biasanya tidak dipatenkan. Di Amerika Serikat, sebuah klaim yang terdiri hanya dari manipulasi sederhana dari konsep abstrak, angka, atau sinyal tidak berarti suatu "process" (SPTO 2006), dan oleh karena itu algoritma tidak bisa dipatenkan (sebagaimana dalam [[Gottschalk v. Benson]]).

Namun, penerapan praktis dari algoritma terkadang dipatenkan.

Sebagai contohnya, dalam [[Diamond v. Diehr]], aplikasi dari algoritma [[umpan-balik]] sederhana untuk membantu dalam menyembuhkan [[karet sintetis]] dianggap dapat dipatenkan.

 

Sebagai tambahan, beberapa algoritma kriptografi memiliki batasan ekspor (lihat [[ekspor dari kriptografi]]).

 

Kata ''"Algoritma"'', atau ''"[[Algorisma]]"'' pada versi penulisan lain, datang dari nama [[al-Khwarizmi]]. dieja dalam Arab klasik sebagai Al-Khwarithmi. Al-khwarizmi ({{lang-fa|خوارزمي}}, 780-850) adalah [[matematikawan]], [[ahli astronomi]], [[ahli geografi]] dari [[orang Persia|Persia]] dan sarjana [[House of Wisdom]] di [[Baghdad]], yang arti namanya ''"penduduk asli [[Khwarezm]]"'', sebuah kota yang merupakan bagian dari [[Wilayah Iran]] pada masanya dan sekarang [[Uzbekistan]].

Sekitar tahun 825, dia menulis risalah dalam bahasa Arab, yang diterjemahkan dalam [[Latin]] pada abad ke-12 dengan judul ''Algoritmi de numero Indorum''.

<ref>{{cite book

}}</ref>

Al-Khwarizmi dulunya adalah matematikawan yang paling banyak dibaca di Eropa pada akhir Abad Pertengahan, pada umum lewat bukunya yang lain, [[Al-Jabr|Aljabar]].

<ref>[http://www-history.mcs.st-and.ac.uk/Extras/Boyer_Foremost_Text.html Foremost mathematical texts in history], according to [[Carl B. Boyer]].</ref>

<ref>Etymology of algorithm at [http://dictionary.reference.com/browse/algorithm Dictionary.Reference.com]</ref>

 

Dalam makna tersebut, algoritima dikenal di Eropa jauh sebelum Al-Kharizmi.

Algoritma paling tua yang dikenal sekarang adalah [[Algoritma Euklid]] (lihat juga [[Pengembangan algoritma Euklid]]).

<ref>Becker O (1933). "Eudoxus-Studien I. Eine voreuklidische Proportionslehre und ihre Spuren bei Aristoteles und Euklid". Quellen und Studien zur Geschichte der Mathematik B 2: 311–333.</ref>

Euclid.

 

=== Asal mula ===

 

 

=== Simbol diskrit dan yang dapat dibedakan ===

 

'''Penanda-penghitung''': Untuk mencatat hewan gembalaan, kumpulan biji dan uang mereka orang dahulu menggunakan penghitung: akumulasi batu atau tanda yang ditoreh pada tongkat, atau membuat simbol diskrit di kerang.

 

=== Manipulasi simbol sebagai "penampung" bilangan: aljabar ===

=== Rancangan mekanis dengan tingkat diskrit ===

 

<ref>Bolter 1984:24</ref>

yang menyediakan kita dengan tik dan tak dari jam mekanis.

<ref>Bolder 1984:26</ref>

mengarah langsung pada "[[teori otomata|otomata]] mekanis" dimulai pada abad ke-13 dan terakhir pada "mesin komputasi" -- [[motor berbeda]] dan [[motor analitik]] dari [[Charles Babbage]] dan bangsawan [[Ada Lovelace]], pertengahan abad ke-19.

 

''Mesin logika 1870 - [[Stanley Jevons]] "sempoa logika" dan "mesin logika"'': Masalah teknisnya adalah untuk mereduksi [[persamaan boolean]] bila ditampilkan dalam sebuah bentuk yang pada masa sekarang dikenal sebagai [[pemetaan Karnaugh]].

Mesinnya dilengkapi dengan "beberapa tangkai kayu yang bisa dipindahkan" dan "di bawah ada 21 kunci seperti pada piano [dll] ...".

Dengan mesin ini dia dapat menganalis sebuah "[[silogisme]] atau argumen logika sederhana apapun".

 

Davis (2000) mengamati pentingnya penyiaran elektromekanis (dengan "keadaan binari"-nya ''buka'' dan ''tutup''):

 

=== Matematika selama abad 19 sampai pertengahan abad 20 ===

 

<ref>van Heijenoort 1967:81ff</ref>

 

''Paradoks'': Pada masa yang sama sejumlah paradoks yang mengganggu muncul dalam literatur, pada khususnya [[paradoks Burali-Forti]] (1987), [[paradoks Russell]] (1902-03), dan [[Paradoks Richard]].

<ref>Dixon 1906, cf. Kleene 1952:36–40</ref>

 

Dalam waktu yang cepat hal berikut muncul: [[kalkulus-λ]] oleh [[Alonzo Church]], [[Stephen Kleene]], dan [[J.B. Rosser]]

<ref>

Kleene 1935–6 in Davis 1965:237ff, Kleene 1943 in Davis 1965:255ff

</ref>

<ref>Church 1936 in Davis 1965:88ff</ref>

bahwa permasalahan keputusan tidak terpecahkan, definisi [[Emil Post]] tentang penghitungan efektif yaitu sebagai pekerja yang tanpa berpikir mengikuti suatu daftar instruksi untuk bergerak ke kiri atau kanan lewat sederetan ruangan dan bersamaan dengan itu bisa menandai atau menghapus kertas atau mengamati kertas dan membuat pilihan ya-tidak tentang instruksi selanjutnya.

Pembuktian Alan Turing bahwa permasalahan keputusan tidak terpecahkan dengan menggunakan "sebuah mesin [otomatis]"-nya

<ref>Turing 1936–7 in Davis 1965:116ff</ref>

<ref>Kleene 1943 in Davis 1965:273–274</ref>

dan beberapa tahun kemudian Kleene menamakan tesisnya "Tesis Church"

=== Emil Post (1936) dan Alan Turing (1936-37, 1939) ===

 

 

[[Emil Post]] (1936) mendeskripsikan aksi dari sebuah "komputer" (manusia) sebagai berikut:

 

Simbol ruangnya yaitu

:"Satu kotak dibiarkan dan disebut sebagai titik awal. ...sebuah masalah tertentu diberikan dalam bentuk simbolik dengan sejumlah kotak terbatas [yaitu, INPUT] ditandai dengan coretan. Begitu juga jawabannya [yaitu, OUTPUT] diberikan dalam bentuk simbolik dari suatu konfigurasi dari kotak-kotak yang ditandai....

 

 

Tapi dia terus maju selangkah ke depan dan membuat sebuah mesin sebagai model dari komputasi angka.

<ref>Turing 1936–7:116</ref>

 

 

:"Perilaku dari komputer disetiap waktu ditentukan oleh simbol yang diobservasinya, dan "keadaan pikiran"-nya pada waktu tersebut. Juga bisa diasumsikan bahwa ada batas B sebagai jumlah simbol atau persegi yang mana komputer dapat amati dalam satu waktu. Jika ia ingin mengamati lebih, ia harus menggunakan pengamatan beriringan. Kita juga memisalkan bahwa jumlah keadaan pikiran yang diperlukan disini adalah terbatas...

 

 

Reduksi Turing menghasilkan hal berikut:

::"(B) Suatu kemungknian perubahan (b) dari persegi yang diamati, bersama dengan kemungkinan perubahan dari keadaan pikiran"

 

 

:"Sebuah fungsi dikatakan "bisa dihitung secara efektif" jika nilainya bisa ditemukan dengan proses yang murni mekanis.

Walau sangat mudah menangkap ide ini, namun ia membutuhkan beberapa definisi matematikan terbatas yang bisa diekspresikan . . . [dia mendiskusikan sejarah dari definisi seperti di atas dengan menghormati Godel, Herbrand, Kleen, Church, Turing dan Post] ... Kita mungkin gunakan pernyataan tersebut secara harfiah, memahami murni dengan proses mekanis yang mana dapat dilakukan oleh sebuah mesin. Memungkinkan untuk memberikan deskripsi matematis, dalam beberapa bentuk normal, dari struktur mesin tersebut. Perkembangan dari ide ini mengarah pada definisi penulis dari sebuah fungsi yang dapat dihitung, dan untuk mengidentifikasi komputibilitas † dengan penghitungan yang efektif . . . .

 

=== J. B. Rosser (1939) dan S. C. Kleene (1943) ===

 

 

Catatan kaki Rosser #5 merujuk karya dari (1) Church dan Kleene dan definisi dari definabiliti-λ, secara khusus Church menggunakannya dalam ''An Unsolvable Problem of Elementary Number Theory''-nya (1936);

''[[Stephen C. Kleene]]'' didefinisikan sebagai "Thesis I"-nya yang terkenal yang dikenal sebagai [[tesis Church-Turing]].

Tapi dia melakukan hal tersebut dalam konteks berikut (penebalan dari aslinya):

 

=== Sejarah setelah 1950 ===

 

{{colbegin|3}}

* [[Mesin abstrak]]

* [[Rekayasa algoritma]]

* ''[[Pendahuluan untuk Algoritma]]''

* [[Daftar topik algoritma umum]]

* [[Numerical Mathematics Consortium]]

* [[Teori komputasi]]

{{colend}}

 

{{Reflist|30em}}

 

{{refbegin|30em}}

* Axt, P. (1959) On a Subrecursive Hierarchy and Primitive Recursive Degrees, ''Transactions of the American Mathematical Society'' 92, pp.&nbsp;85–105

* Bell, C. Gordon and Newell, Allen (1971), ''Computer Structures: Readings and Examples'', McGraw-Hill Book Company, New York. ISBN 0-07-004357-4.

* {{Cite journal|author1-link=Andreas Blass|first1=Andreas|last1=Blass|author2-link=Yuri Gurevich|first2=Yuri|last2=Gurevich|year=2003|url=http://research.microsoft.com/~gurevich/Opera/164.pdf|title=Algorithms: A Quest for Absolute Definitions|journal= Bulletin of European Association for Theoretical Computer Science|volume= 81}} Includes an excellent bibliography of 56 references.

* Campagnolo, M.L., [[Cris Moore|Moore, C.]], and Costa, J.F. (2000) An analog characterization of the subrecursive functions. In ''Proc. of the 4th Conference on Real Numbers and Computers'', Odense University, pp.&nbsp;91–109

* {{Cite journal|last=Church|first=Alonzo|authorlink=Alonzo Church|title=An Unsolvable Problem of Elementary Number Theory|journal=The American Journal of Mathematics|volume=58|pages= 345–363|year=1936a|doi=10.2307/2371045|issue=2|jstor=2371045}} Reprinted in ''The Undecidable'', p.&nbsp;89ff. The first expression of "Church's Thesis". See in particular page 100 (''The Undecidable'') where he defines the notion of "effective calculability" in terms of "an algorithm", and he uses the word "terminates", etc.

{{refend}}

 

{{wiktionary}}

{{wikibooks|Algorithma}}

* {{en}} {{springer|title=Algorithm|id=p/a011780}}

* {{dmoz|Computers/Algorithms/|Algorithms}}

* {{en}} [http://www.nist.gov/dads/ Dictionary of Algorithms and Data Structures]—[[National Institute of Standards and Technology]]

* {{en}} [http://www.softpanorama.org/Algorithms/index.shtml Algorithms and Data Structures by Dr Nikolai Bezroukov]

 

[[Kategori:Algoritma| ]]

[[Kategori:Logika matematika]]