Diagram alur dari sebuah algoritme (Algoritme Euclid) untuk menghitung faktor persekutuan terbesar (f.p.b.) dari dua angka a dan b dalam lokasi bernama A dan B. Algoritme dijalankan dengan pengurangan berturut-turut dalam dua pengulangan: JIKA pengujian B >= A menghasilkan "ya" (atau benar) (lebih akuratnya angka b dalam lokasi B lebih besar atau sama dengan angka a dalam lokasi A) MAKA, algoritme menentukan B ← B - A (artinya angka b - a menggantikan b sebelumnya). Hal yang sama, JIKA A > B, MAKA A ← A - B. Proses tersebut berhenti saat (isi dari) B adalah 0, menghasilkan f.p.k. dalam A. (Algoritme tersebut diambil dari Scott 2009:13; simbol dan gaya penggambaran dari Tausworthe 1977).Sejarah Lengkap:
Kata algoritme datang dari nama matematikawan Persia abad ke-9 Abu Abdullah Muhammad ibnu Musa Al-Khwarizmi, yang hasil kerjanya dibangun dari matematikawan India abad ke-7 Brahmagupta. Kata algorisma awalnya mengacu hanya pada aturan-aturan dalam melakukan aritmetika menggunakan bilangan Hindu-Arab namun berkembang lewat penerjemahan Latin Eropa dari nama Al-Khwarizmi menjadi algoritme pada abad ke-18. Penggunaan kata tersebut berkembang mengikutkan semua prosedur untuk menyelesaikan masalah atau melakukan unit kegiatan. [65]
Simbol diskrit dan yang dapat dibedakanSunting
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. Sampai orang Babilonia dan Mesir menggunakan tanda dan simbol, pada akhirnya bilangan Roma dan abakus berkembang (Dilson, p. 16-41). Penanda penghitung muncul dalam sistem bilangan operan aritmetika digunakan dalam mesin Turing dan komputasi mesin Post-Turing.
Manipulasi simbol sebagai "penampung" bilangan: aljabarSunting
Karya dari Geometer Yunani kuno (algoritme Euklid), matematikawan India Brahmagupta, dan matematikawan Persia Al-Khwarizmi (yang darinya isitlah "algorism" dan "algoritme" diturunkan), dan matematikawan Eropa Barat memuncak dalam notasi Leibniz dari rasiosinator kalkulus (sekitar 1680-an):
Abad yang baik dan setengah lebih maju dari masanya, Leibniz mengajukan logika aljabar, sebuah aljabar yang akan menentukan aturan-aturan untuk memanipulasi konsep logika dengan cara yang aljabar biasa menentukan aturan untuk manipulasi angka.[66]
Rancangan mekanis dengan tingkat diskritSunting
Jam: Bolter memuji penemuan jam gaya-berat sebagai "Kunci penemuan dari Eropa pada Abad Pertengahan", khususnya pada ambang pelarian [67] yang menyediakan kita dengan tik dan tak dari jam mekanis. "Mesin otomatis yang akurat" [68] mengarah langsung pada "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. [69] Lovelace dikreditkan sebagai yang pertama menciptakan algoritme yang ditujukan untuk diproses di komputer—motor analitis Babbage, perangkat pertama yang dianggap komputer Turing-sempurna sebenarnya bukan hanya sebuah kalkulator—dan terkadang dikenal "programmer pertama dalam sejarah", walaupun implementasi penuh dari perangkat Babbage kedua tidak terealisasi sampai beberapa dekade setelah masanya.
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. Jevons (1880) pertama menjelaskan "sempoa" sederhana dari "potongan kayu dilengkapi dengan penyemat, dibuat supaya bagian atau kelas kombinasi logika manapun dapat dipilih secara mekanis ... Baru-baru ini Saya telah mereduksi sistem menjadi bentuk yang secara sempurna mekanis, dan membuatnya mewujudkan keseluruhan proses inferensi tak langsung dalam apa yang disebut sebuah Mesin Logika" 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". [70]
Mesin tenun Jacquard, kartu berlobangnya Hollerith, telegraf dan telepon -- penyiaran elektromekanis: Bell dan Newell (1971) mengindikasikan bahwa mesin tenun Jacquard (1801), pelopor dari kartu Hollerith (kartu berlobang, 1887), dan "teknologi alih telepon" adalah akar dari sebuah pohon yang mengarah pada perkembangan dari komputer pertama. [71] Pada pertengahan abad ke-19 telegraf, pelopor dari telepon, digunakan diseluruh dunia, pengkodean diskrit dan pembedaan huruf sebagai "titik dan strip". Pada akhir abad ke-19 pita telegraf (sekitar 1870-an) digunakan, sebagaimana juga kartu Hollerith pada sensus Amerika 1890. Kemudian muncullah teleprinter (sekitar 1910-an) dengan kerta-berlobang menggunakan kode Baudot di pita.
Jaringan alih-telepon dari penyiaran elektromekanis (ditemukan 1835) adalah karya dair George Stibitz (1937), penemu dari perangkat penghitungan digital. Saat bekerja di laboratorium Bell, dia mengamati "beratnya" penggunaan kalkulator mekanis dengan geligi. "Dia pulang ke rumah pada suatu malam 1937 berniat untuk menguji idenya ... Saat mengatik selesai, Stibitz telah membangun perangkat hitung digital". [72]
Davis (2000) mengamati pentingnya penyiaran elektromekanis (dengan "keadaan binari"-nya buka dan tutup):
- Hanya dengan perkembangan, dimulai sejak 1930-an, dari kalkulator elektromekanis menggunakan penggantian elektris, sehingga mesin yang dibuat memiliki ruang lingkup yang dibayangkan Babbage."[73]
Matematika selama abad 19 sampai pertengahan abad 20Sunting
Simbol dan aturan: Dengan cepat berkembangnya matematika dari George Boole (1847, 1854), Gottlob Frege (1897), dan Giuseppe Peano (1888-1889) mereduksi aritmetika menjadi serangkaian simbol dimanipulasi oleh aturan-aturan. The Principles of arithmetic, presented by a new method-nya Peano (1888) adalah "usaha pertama mengaksiomakan matematika dalam sebuah bahasa simbolik". [74]
Tapi Heijenoort memberi pujian pada Frege (1879): Frege "merupakan karya tulis paling penting mengenai logika. ... yang mana kita lihat sebuah "'bahasa formula', yaitu sebuah lingua characterica, sebuah bahasa ditulis dengan simbol-simbol khusus, "untuk berpikir murni", yaiut, bebas dari hiasan retorikal ... dibangun dari simbol-simbol tertentu yang dimanipulasi menurut aturan-aturan terbatas". [75] Karya dari Frege lebih lanjut disederhanakan dan diperkuat oleh Alfred North Whitehead dan Bertrand Russell dalam Principia Mathematical (1910-1913).
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. [76] Hasilnya mengarah ke makalah Kurt Godel (1931) -- dia secara khusus merujuk paradoks pembohong—yang mereduksi aturan dari rekursi pada angka.
Penghitungan Efektif: Dalam usaha untuk menyelesaikan permasalahan keputusan yang didefinisikan oleh Hilbert tahun 1928, matematikawan pertama mendefinisikan apa arti dari "metode efektif" atau "kalkulasi efektif" (misalnya, sebuah kalkulasi yang akan sukses). Dalam waktu yang cepat hal berikut muncul: kalkulus-λ oleh Alonzo Church, Stephen Kleene, dan J.B. Rosser [77] definisi dari "rekursi umum" yang benar-benar diasah dari karya Godel berdasarkan saran dari Jacquard Herbrand (cf. kuliah Godel di Princeton tahun 1934) dan penyederhaan selanjutnya oleh Kleene. [78] Church membuktikan [79] 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. [80] Pembuktian Alan Turing bahwa permasalahan keputusan tidak terpecahkan dengan menggunakan "sebuah mesin [otomatis]"-nya [81] dengan efek yang mirip dengan "formulasi"-nya Post, definisi J. Barkley Rosser tentang "metode efektif" dalam makna "sebuah mesin". [82] Proposal S. C. Kleene dari pelopor "Tesis Church" yang disebutnya "Thesis I", [83] dan beberapa tahun kemudian Kleene menamakan tesisnya "Tesis Church" [84] dan mengajukan "Tesis Turing". [85]
Emil Post (1936) dan Alan Turing (1936-37, 1939)Sunting
Berikut adalah kebetulan yang luar biasa dari dua orang yang tidak saling mengenal tetapi mendeskripsikan sebuah proses orang-sebagai-komputer mengerjakan perhitungan—dan mereka menghasilkan definisi yang mirip.
Emil Post (1936) mendeskripsikan aksi dari sebuah "komputer" (manusia) sebagai berikut:
- "... dua konsep ikut serta: yaitu sebuah simbol ruang dimana pekerjaan yang mengarah dari masalah ke jawaban dilakukan, dan sekumpulan arahan yang baku dan tidak bisa diubah.
Simbol ruangnya yaitu
- "sederetan dua arah tak terbatas dari ruang atau kotak... penyelesai masalah atau pekerja harus berjalan dan bekerja di simbol ruang ini, dengan bisanya [si pekerja] masuk, dan beroperasi dengan satu kotak dalam satu waktu... sebuah kotak memiliki dua kemungkinan kondisi, yaitu, kosong atau belum ditandai, dan dengan adanya tanda tunggal disana, katakanlah garis vertikal.
- "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....
- "Sekumpulan arahan bisa digunakan untuk permasalahan umum menentukan proses determistik saat diterapkan pada setiap masalah tertentu. Proses ini hanya berhenti bila datang arahan dengan tipe (C ) [yaitu, STOP]".[86] Lihat lebih lanjut pada mesin post-TuringKarya Alan Turing[87] mendahului karya dari Stibitz (1937); tidak diketahui apakah Stibitz mengetahui karya Turing. Biografinya Turing percaya bahwa Turing menggunakan model seperti-mesin-ketik diturunkan dari ketertarikannya pada masa muda: "Alan memiliki impian menemukan mesin ketik pada saat muda; Ibu Turing memiliki sebuah mesin ketik; dan dia mungkin memulainya dengan menanyakan pada dirinya sendiri apa maksudnya dengan menyebut sebuah mesin ketik dengan 'mekanikal'".[88] Dengan lazimnya kode Morse dan telegraf, mesin pita telegraf, dan mesin-ketik jarak jauh pada waktu itu kita bisa menyimpulkan bahwa semua itu memberikan pengaruh.
Turing—model dari komputasinya sekarang dikenal dengan mesin Turing—memulai, sebagaimana Post, dengan analisis dari komputer manusia yang ia sederhanakan menjadi sekumpulan gerakan dasar sederhana dan "keadaan pikiran". Tapi dia terus maju selangkah ke depan dan membuat sebuah mesin sebagai model dari komputasi angka. [89]
- "Menghitung biasanya dilakukan dengan menulis simbol tertentu di atas kertas. Misalkan kertas tersebut dibagi menjadi segi empat seperti buku aritmetika anak-anak.... Saya asumsikan bahwa komputasi dilakukan pada kertas satu dimensi, yaitu, di pita yang dibagi dalam persegi. Juga misalkan bahwa jumlah simbol yang akan dicetak terbatas....
- "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...
- "Mari kita bayangkan bahwa operasi yang dilakukan oleh komputer akan dipecah menjadi 'operasi-operasi sederhana' yang sangat mendasar sehingga tidak mudah membayangkannya untuk dibagi lebih jauh."[90]
Reduksi Turing menghasilkan hal berikut:
- "Operasi sederhana haruslah mengikutkan:
- "(a) Perubahan dari simbol pada salah satu persegi yang sedang diamati
- "(b) Perubahan dari salah satu persegi diamati terhadap persegi lainnya di antara L persegi dari salah satu yang sebelumnya diamati.
"Bisa saja beberapa dari perubahan tersebut menyebabkan perubahan keadaan pikiran. Operasi tunggal paling umum oleh karena itu harus diambil jadi salah satu hal berikut:
- "(A) Suatu kemungkinan perubahan (a) dari simbol bersamaan dengan suatu perubahan dari keadaan pikiran.
- "(B) Suatu kemungknian perubahan (b) dari persegi yang diamati, bersama dengan kemungkinan perubahan dari keadaan pikiran"
- "Kita sekarang mungkin sudah bisa membentuk sebuah mesin untuk melakukan pekerjaan dari komputer tersebut."[90]
Beberapa tahun kemudian, Turing mengembangkan analisisnya (tesis, secara definisi) dengan ekspresi kuat berikut:
- "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 . . . .
- "† Kita boleh menggunakan ekspresi "fungsi hitung" untuk mengartikan sebuah fungsi yang dapat dihitung oleh sebuah mesin, dan kita biarkan "secara efektif dapat dihitung" mengacu pada ide intuitif tanpa definisi tertentu dengan salah satu dari definisi tersebut".[91]
J. B. Rosser (1939) dan S. C. Kleene (1943)Sunting
J. Barkley Rosser mendefinisikan 'metode [matematis] efektif' dengan cara berikut (kemiringan ditambahkan):
- "'Metode efektif' disebut sebagai metode yang spesial yang mana setiap langkahnya secara tepat ditentukan dan pasti menghasilkan jawaban dalam sejumlah langkah yang terbatas. Dengan pengertian khusus ini, tiga definisi berbeda telah diajukan sampai sekarang. [catatan kakinya #5; lihat diskusinya di bawah]. Yang paling sederhana (karena Post dan Turing) menyatakan intinya bahwa sebuah metode efektif menyelesaikan sekumpulan permasalahan hanya ada jika seseorang bisa membuat sebuah mesin yang akan menyelesaikan setiap masalah dari sekumpulan masalah tanpa campur tangan manusia kecuali memasukan pertanyaan dan (nantinya) membaca jawabannya. Ketiga definisi tersebut sama, jadi tidak masalah yang mana yang digunakan. Lebih lanjut, fakta bahwa ketiganya sama adalah argumen yang sangat kuat untuk kebenaran dari salah satunya." (Rosser 1939:225-6)
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); (2) Herbrand dan Godel dan penggunaan rekursi mereka terutama Godel menggunakannya dalam makalah terkenalnya On Formally Undecidable Propositions of Principia Mathematica and Related Systems I (1931); dan (3) Post (1936) dan Turing (1936-7) dalam model mekanisme komputasi mereka.
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):
- "12. Teori-teori algoritme... Dalam menyiapkan sebuah teori algoritme yang komplet, apa yang kita lakukan adalah mendeskripsikan sebuah prosedur, yang dapat dilakukan untuk setiap kumpulan nilai dari variabel-variabel tunggal, yang mana prosedur berhenti dan dengan cara tersebut dari hasilnya kita bisa membaca sebuah jawaban tertentu, "ya" atau tidak", untuk pertanyaan "apakah nilai predikat benar?"" (Kleene 1943:273)
Sejarah setelah 1950Sunting
Sejumlah usaha telah diarahkan untuk memperbaiki lebih lanjut definisi dari "algoritme", dan aktivitas tersebut masih terus berjalan karena isu-isu yang mengelilinginya, terutama, fondasi matematika (khususnya tesis Church-Turing) dan filsafat pikiran (khususnya argumen menyangkut kecerdasan buatan).
