Algoritma

Dalammatematikadanilmu komputer,algoritmaadalah rangkaian terbatas dari instruksi-instruksi yang rumit, biasanya digunakan untuk menyelesaikan atau menjalankan suatu kelompok masalahkomputasitertentu. Algoritma digunakan sebagai spesifikasi untuk melakukan perhitungan dan pemrosesandata. Algoritma yang lebih mutakhir dapat melakukandeduksiotomatis (disebut sebagai penalaran otomatis) dan menggunakan tes matematis dan logis untuk mengarahkan eksekusi kode melalui berbagai rute (disebut sebagai pengambilan keputusan otomatis). Penggunaan karakteristik manusia sebagai deskriptor mesin secara metaforis telah dipraktekkan olehAlan Turingdengan terminologi seperti "memory", "search" dan "stimulus".
Sebaliknya,heuristikaadalah pendekatan untuk pemecahan masalah komputasi yang mungkin tidak sepenuhnya terspesifikasi atau tidak menjamin hasil yang benar atau optimal, terutama dalam ranah masalah komputasi yang mana tidak ada hasil yang benar atau optimal yang terdefinisi dengan baik.
Sebagai metode yang efektif, algoritma dapat diekspresikan dalam jumlah ruang dan waktu yang terbatas,dan dalambahasa formalyang terdefinisi dengan baikuntuk menghitung suatufungsi.Dimulai dari tataran awal dan input awal (bisa jadi kosong),instruksi-instruksi yang ada menggambarkan sebuah komputasi yang, ketika dieksekusi, berjalan melalui sejumlah tataran dengan jumlah terhingga yang terdefinisi dengan baik,yang pada akhirnya menghasilkan "output"dan berakhir pada tataran final akhir. Transisi dari satu tataran ke tataran berikutnya tidak selalu bersifat menentukan; beberapa algoritma, yang dikenal sebagai algoritma acak, menggabungkan input acak.
Konsep algoritma telah ada sejak zaman prasejarah. Algoritmaaritmatika, seperti algoritma divisi, digunakan oleh matematikawanBabiloniakuno sekitar tahun 2500SMdan matematikawanMesirsekitar tahun 1550 SM. MatematikawanYunanikemudian juga menggunakan algoritma pada 240 SM sebagaimana yang terdapat padaTapis Eratosthenesuntuk menemukan bilangan prima, danAlgoritma Euklidesuntuk menemukan pembagi persekutuan terbesar dari dua bilangan.Matematikawan Arab sepertial-Kindipada abad ke-9 menggunakan algoritma kriptografi untuk pemecahan kode, berdasarkan analisis frekuensi.
Kata algoritma berasal dari nama matematikawanPersiaabad ke-9,Muḥammad bin Mūsā al-Khwārizmī, yangnisbah-nya (yang mengidentifikasikannya sebagai seseorang yang berasal dariKhwarezmia) dilatinkan sebagai Algoritmi (bahasa Persia yang diarabkan: الخوارزمی sekitar: 780-850).Namanya bermakna 'yang berasal dari (daerah)Khwarezmia', sebuah daerah yang dulunya merupakan bagian dariIran Rayadan sekarang sebagai bagian dariUzbekistan.Sekitar tahun 825, Al-Khwarizmi menulis sebuah risalahberbahasa Arabtentangsistem angka Hindu-Arab, yang diterjemahkan ke dalambahasa Latinselama abad ke-12. Naskah ini dimulai dengan frasa Dixit Algorizmi ('Maka berkatalah Al-Khwarizmi'), di mana "Algorizmi" di sini adalahLatinisasipenerjemah akan nama Al-Khwarizmi.Bukunya yang bernama Aljabar menjadi salah satu buku matematikawan yang paling banyak dibaca di Eropa pada abad pertengahan.Dalam bahasa Latin abad pertengahan, kataalgorismus,yang merupakan pengadaptasian dari namanya, menjadi kata yang bermakna "sistem bilangan desimal".Pada abad ke-15, di bawah pengaruh kata Yunani ἀριθμός (arithmos), 'angka' (lih. 'aritmatika'), kata Latin-nya diubah menjadi algorithmus.Dalambahasa Inggris, kata algorithm pertama kali digunakan pada sekitar tahun 1230 dan kemudian olehChaucerpada 1391. Bahasa Inggris mengadopsi istilah tersebut daribahasa Prancis, akan tetapi baru pada abad ke-19 lah kata "algorithm" mulai memiliki makna seperti sekarang yang ada dalam bahasa Inggris modern.
MatematikaIndiapada awalnya sebagian besar berbentuk algoritmik. Algoritma yang mewakili tradisi matematika India berkisar dari Śhulba Sūtrā dari beberapa abad sebelum masehi hingga teks-teks abad pertengahan dari Sekolah Kerala akan Astronomi dan Matematika.
Pemakaian awal lainnya dari kata ini berasal dari tahun 1240, dalam sebuahmanualberjudul Carmen de Algorismo yang disusun oleh Alexandre de Villedieu. Yang kalimatnya diawali dengan:
yang bermakna:
Puisi ini panjangnya beberapa ratus baris dan merangkum ilmu menghitung dengan angka-angka yang diadopsi dariIndia.
Formalisasi parsial dari konsep algoritma modern dimulai dengan upaya untuk memecahkanEntscheidungsproblem(masalah pengambilan keputusan) yang diajukan olehDavid Hilbertpada tahun 1928. Formalisasi selanjutnya dibingkai sebagai upaya untuk mendefinisikan "kalkulabilitas efektif"atau "metode efektif".Formalisasi tersebut termasuk fungsi rekursifGödel-Herbrand-Kleene pada tahun 1930, 1934 dan 1935,kalkuluslambda Alonzo Church pada tahun 1936, Formulasi 1 Emil Post pada tahun 1936, danmesin Turing-nyaAlan Turingpada tahun 1936-37 dan 1939.
Definisi informalnya bisa berarti "sekumpulan aturan yang secara tepat menentukan seurutan operasi".yang mengikutkan semua program komputer, termasuk program yang tidak melakukan perhitungan numerik.
Secara umum, sebuah program hanyalah sebuah algoritma jika ia akan berhenti nantinya.
Sebuah contoh prototipikal dari suatu algoritma adalahalgoritma Eucliduntuk menentukan bilangan pembagi terbesar dari dua integer; sebagai contohnya (ada contoh yang lain) dijelaskan dengandiagram alurdi atas dan sebagai contoh di bagian lanjut.
(Boolos & Jeffrey 1974, 1999) memberikan sebuah makna informal dari kata algoritma dalam persamaan berikut:
Suatu "bilangan tak-terbatas" adalah bilangan yang elemen-elemenya bisa berkorespondensi satu-ke-satu dengan integer.
Maka, Boolos dan Jeffrey mengatakan bahwa sebuah algoritma berarti instruksi bagi sebuah proses yang "membuat" keluaran integer dari sebuah "masukan"acakinteger yang, secara teori, bisa sangat besar.
Maka sebuah algoritma dapat berupapersamaan aljabarsepertiy = m + n-- dua variabel masukanmdannyang menghasikan keluarany.
Tapi berbagai penulis yang mencoba mendefinisikan persamaan tersebut mengatakan bahwa kata algoritma mengandung lebih dari itu, sesuatu yang kurang lebih (untuk contoh penjumlahan):
Konsep darialgoritmajuga digunakan untuk mendefinisikan notasi daridesidabilitas.
Notasi tersebut adalah pusat untuk menjelaskan bagaimanasistem formalberasal dari sejumlah kecilaksiomadan aturan.
Dalamlogika, waktu dari sebuah algoritma untuk selesai tidak dapat dihitung, karena tidak berelasi dengan dimensi fisik kita.
Dari ketidakpastian tersebut, yang mengkarakteristikan pekerjaan yang sedang berjalan, timbulah ketidak-tersediannya definisialgoritmayang sesuai dengan konkret (pada tingkat tertentu) dan penggunaan secara abstrak dari istilah tersebut.
Algoritma sangat penting bagi cara komputer mengolah data.
Banyakprogram komputermengandung algoritma memberikan rincian pada instruksi khusus yang komputer harus lakukan (dengan urutan tertentu) untuk menjalankan pekerjaan tertentu, seperti menghitung gaji karyawan atau mencetak kartu rapor siswa.
Maka, sebuah algoritma bisa dianggap sebagaiurutan operasiyang bisa disimulasikan oleh sebuah sistemTuring-lengkap.
Penulis yang mendukung tesis ini termasuk Minsky (1967), Savage (1987), dan Gurevich (2000):
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.
Pada praktiknya, keadaan tersebut disimpan pada satu atau lebihstruktur data.
Untuk beberapa proses komputasi, algoritma harus ditentukan secara teliti: dijabarkan dengan cara ia bakal berlaku untuk semua kemungkinan yang dapat timbul.
Yaitu, setiap langkah tambahan harus secara sistematis dihadapi, kasus-per-kasus;
Kriteria bagi setiap kasus harus jelas (dan bisa dihitung).
Karena sebuah algoritma adalah kumpulan dari langkah-langkah yang tepat, urutan dari komputasi selalu penting bagi berfungsinya algoritma.
Instruksi biasanya diasumsikan terdaftar secara eksplisit, dan dijelaskan dimulai "dari atas" dan terus "ke bawah", sebuah gambaran yang dijelaskan secara formal olehalur kontrol
Sejauh ini, diskusi tentang formalisasi algoritma telah mengasumsikan premis daripemrograman imperatif.
Hal ini merupakan konsepsi umum, yang mencoba menjelaskan sebuah pekerjaan dalam makna diskrit dan "mekanis".
Keunikan dari konsepsi formalisasi algoritma adalahoperasi penetapan, mengatur nilai dari sebuah variabel.
Ia berasal dari intuisi "ingatan" sebagai kertas buram.
Contoh operasi penetapan tersebut ada di bawah.
Untuk konsepsi yang lain dari apa yang membentuk sebuah algoritma lihatpemrograman fungsionaldanpemrograman logika.
Algoritma dapat digambarkan dengan banyak notasi, termasukbahasa alamiah,pseudokode,diagram alur,bagan drakon,bahasa pemrogramanatautabel kontrol(diproses olehpenerjemah).
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.
Bahasa pemrograman ditujukan untuk mengekspresikan algoritma dalam sebuah bentuk yang dapat dieksekusi oleh komputer, tetapi sering kali digunakan sebagai suatu cara untuk menentukan atau mendokumentasikan algoritma.
Ada banyak macam kemungkinan representasi dan seseorang dapat mengekspresikan sebuah programmesin Turingsebagai urutan dari tabel-tabel mesin (lihat lebih lanjut dimesin kondisi-terbatas,tabel transisi kondisidantabel kontrol), sebagai diagram alur dan bagan drakon (lihat lebih lanjut didiagram kondisi), atau sebagai bentukkode mesinataukode assemblydasar yang dikenal "kumpulan lipat empat" (lihat lebih lanjut dimesin Turing).
Representasi dari algoritma dapat dikelompokan ke dalam tiga tingkatan dari deskripsi mesin Turing:
Sebagai contoh dari algoritma sederhana "Penjumlahan m+n" dijelaskan dalam tiga tingkatan tersebut lihatcontoh algoritma.
Kebanyakan algoritma ditujukan untuk diimplementasikan sebagaiprogram komputer.
Namun, algoritma juga diimplementasikan dengan tujuan lain, seperti dalamjaringan sarafbiologis (sebagai contohnya,otak manusiayang mengimplementasikanaritmetikaatau sebuahseranggayang melihat makanan), dalamsirkuit elektris, atau dalam sebuah perangkat mekanis.
Dalamsistem komputer, sebuah algoritma pada dasarnya adalah instansi darilogikaditulis dalamperangkat lunakoleh pengembang perangkat lunak supaya efektif untuk komputer yang "ditargetkan" untuk mesin tertentu untuk menghasilkankeluarandarimasukanyang 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:
Chaitin membuka definisinya dengan: "Saya akan perlihatkan bahwa anda tidak dapat membuktikan sebuah program adalah 'elegan'"—bukti tersebut akan menyelesaikanpermasalahan perhentian(ibid).
Algoritma terhadap fungsi yang dapat dihitung oleh algoritma: Untuk sebuah fungsi bisa ada beberapa algoritma.
Hal ini benar, bahkan tanpa mengembangkan kumpulan instruksi yang ada bagi programmer.
Rogers mengamati bahwa "Sangat ... penting untuk membedakan antara pengertianalgoritma, misalnya prosedur dan pernyataanfungsi yang dihitung oleh algoritma, misalnya pemetaan hasil dari prosedur.
Fungsi yang sama bisa memiliki beberapa algoritma berbeda".
Sayangnya ada pertukaran antara kebaikan (kecepatan) dan elegan (kepadatan) -- sebuah program yang elegan bisa melakukan lebih banyak langkah untuk menyelesaikan sebuah komputasi daripada yang kurang elegan.
Sebuah contoh yang menggunakan algoritma Euclid bisa dilihat di bawah.
Komputer (dan komputor), model dari komputasi: Sebuah komputer (atau manusia "komputor")
adalah tipe terbatas dari mesin, sebuah "perangkat mekanis deterministik diskrit"yang secara buta mengikuti instruksinya.Model primitif dari Melzak dan Lambekmereduksi pemikiran tersebut menjadi empat elemen: (i) diskrit,lokasiyang bisa dibedakan,
(ii) diskrit,penghitungyang tak bisa dibedakan(iii) sebuah agen, dan
(iv) sebuah daftar instruksi yangefektifrelatif terhadap kemampuan dari agen.
Minsky menjelaskan variasi yang lebih sesuai dari model "abacus"-nya Lambek dalam "BasisKomputabilitasPaling Sederhana".Mesin Minskymemproses secara berurutan lewat lima (atau enam tergantung bagaimana seseorang menghitungnya) instruksi kecuali baik sebuah kondisi IF-THEN GOTO atau GOTO tak bersyarat mengubah alur program keluar dari urutan.
Selain HALT, mesin Minsky mengikutkan tiga operasipenetapan(penggantian, substitusi):ZERO (misalnya, isi dari lokasi diganti oleh 0: L ← 0), SUCCESSOR (misalnya, L ← L+1), dan DECREMENT (misalnya, L ← L-1).Jarang seorang programer harus menulis "kode" dengan kumpulan instruksi terbatas.
Tapi Minsky memperlihatkan (sebagaimana Melzak dan Lambek) bahwa mesinnya adalahTuring kompletdengan hanya empattipeinstruksi utama: GOTO kondisional, GOTO tak bersyarat, penetapan/penggantian/substitusi, dan HALT.
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 mengeksekusisecara efektif.
Stone memberikan contoh dari hal ini: saat menghitung akar dari persamaan kuadrat si komputor harus tahu bagaimana mendapatkan akar kuadrat.
Jika tidak maka supaya algoritma dapat efektif ia harus menyediakan sejumlah aturan untuk mengekstrak akar kuadrat.
Hal ini berarti programer harus tahu sebuah "bahasa" yang efektif relatif terhadap target pada agen komputasi (komputer/komputor).
Lalu model apa yang seharusnya digunakan untuk simulasi?
Van Emde Boas mengamati "bahkan bila kita mendasariteori kompleksitasdengan mesin abstrak bukannya mesin kongkrit, kesembarangan dari pemilihan model masih tetap ada.
Pada titik itulah mulainya pemikiransimulasi".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").
Pemrograman terstruktur, struktur kanonikal: MenurutTesis Church-Turingsetiap algoritma bisa dihitung dengan sebuah model yang dikenalTuring komplet, dan menurut demonstrasi Minsky kekomplitan Turing membutuhkan hanya empat tipe instruksi—GOTO bersyarat, GOTO tak bersyarat, penetapan, HALT.
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".Tausworthe menambahkan tigastruktur kanon Bohm-Jacopini:SEQUENCE, IF-THEN-ELSE, dan WHILE-DO, dengan dua lagi: DO-WHILE dan CASE.Keuntungan dari program terstruktur adalah ia cocok denganpembuktian kebenaranmenggunakaninduksi matematika.
Simbol diagram alur: Pembantu grafik yang disebutdiagram alurmemberikan suatu cara untuk menjelaskan dan mendokumentasikan sebuah algoritma (dan program komputer).
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).
Struktur kanonikal Bohm-Jacopini dibuat dari bentuk-bentuk primitif tersebut.
Sub-struktur bisa "bersarang" dalam segi empat hanya jika jalan keluar tunggal terjadi pada super-struktur.
Simbol dan penggunaannya untuk membangun struktur kanonikal diperlihatkan dalam diagram.
Salah satu dari algoritma sederhana adalah menemukan bilangan terbesar dalam sebuah deretan angka (tak berurut).
Solusinya membutuhkan pemeriksaan setiap angka dalam deret, tetapi hanya sekali.
Dari hal ini munculah algoritma sederhana, yang bisa dinyatakan dalam kalimat bahasa deskripsi tingkat-tinggi, sebagai:
Deskripsi tingkat-tinggi:
Deskripsi (Quasi-)formal:Ditulis dalam kalimat yang lebih dekat dengan bahasa tingkat-tinggi dari program komputer, berikut ini adalah kode formal dari algoritma dalampseudokodeataukode pijin:
AlgoritmaEuclidmuncul sebagai Proposisi II dalam Book VII ("Elementary Number Theory") dariElements.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.
Dan "mengukur" adalah menempatkan ukuran panjang terkecilsdengan tepat (qkali) di antara ukuran terpanjanglsampai sisarlebih kecil dari panjang terkecils.Dalam dunia modern, sisar = l - q*s,qsebagai hasil bagi, atau sisaradalah "modulus", bagian sisa-integer yang tersisa setelah pembagian.
Supaya metode Euclid berhasil, panjang awalnya harus memenuhi dua kebutuhan:
(i) panjangnya tidak 0, DAN
(ii) hasil pengurangan harus "lebih", sebuah pengujian harus menjamin bahwa bilangan terkecil dari dua angka adalah hasil pengurangan dari yang terbesar (cara lain, keduanya bisa sama sehingga pengurangan menghasilkan 0).
Pembuktian asli Euclid mengikutkan kebutuhan yang ketiga: kedua panjang bukanlah bilangan prima.
Euclid menentukan hal ini supaya dia bisa membentuk sebuah buktireductio ad absurdumbahwa dua pembagi dua angka adalah yangterbesar.Walau algoritma Nicomachus sama dengan Euclid, bila kedua bilangan prima maka menghasilkan angka "1" untuk bilangan pembagi terbesar.
Jadi untuk lebih jelasnya algoritma berikut adalah algoritma Nicomachus.
Hanya beberapatipeinstruksi yang dibutuhkan untuk mengeksekusi algoritma—beberapa tes logika (GOTO bersyarat), GOTO tak bersyarat, penetapan (penggantian), dan pengurangan.
Algoritma berikut disebut sebagai versi Euclid dan Nichomachus 4-langkah-nya Knuth, tetapi bukannya menggunakan pembagi untuk menentukan sisa ia menggunakan pengurangan berturut-turut dari panjang terkecilsdari sisa panjangrsampairkurang daris.
Deskripsi tingkat-tinggi, diperlihatkan dengan tulisan tebal, diadaptasi dari Knuth 1973:2-4:
INPUT:
E0: [Pastikanr≥s.]
E1: [Cari sisa]: Sampai sisa panjangrdi R kurang dari panjang terkecilspada S, kurangi angkasdalam S berulang kali dari sisa panjangrdalam R.
E2: [Apakah sisa 0?]: APAKAH (i) pengukuran terakhir adalah sama dan sisa di R adalah 0 program dapat berhenti, ATAU (ii) algoritma harus terus jalan: hasil pengukuran meninggalkan sisa di R kurang dari angka pengukuran dalam S.
E3: [Interchangesdanr]: Sulitnya algoritma Euclid. Menggunakan sisaruntuk mengukur angka terkecil sebelumnyas:; L sebagai lokasi sementara.
OUTPUT:
DONE:
Versi algoritma Euclid berikut hanya membutuhkan 6 instruksi inti untuk melakukan 13 langkah pada solusi "inelegan"; parahnya, "inelegan" membutuhkantipeinstruksi lebih banyak.
Diagram alur dari "elegan" bisa dilihat pada bagian atas artikel ini.
Dalam bahasa Basic (tak terstruktur) langkahnya diberi nomor, dan instruksi LET [] = [] adalah instruksi penetapan disimbolkan dengan ←.
Bagaimana cara kerja "Elegan": Sebagai pengganti "pengulangan Euclid" luar, "Elegan" mengulang antara dua pengulangan, pengulangan A > B yang menghitung A ← A - B, dan pengualang B ≤ A yang menghitung B ← B - A.
Hal ini bekerja karena, saat yang dikurang M lebih kecil pengurang S ( Selisih = pengurang - yang_di_kurang ), yang_dikurang bisa menjadis(panjang pengukuran yang baru) dan pengurang bisa menjadiryang baru (panjang yang akan diukur);
dengan kata lain "arti" dari pengurangan dibalik.
Apakah algoritma berjalan seperti yang penulis inginkan?
Beberapa kasus uji cukup menentukan fungsi inti.
Sumber pertamamenggunakan 3009 dan 884.
Knuth menyarankan 40902, 24140.
Kasus menarik lainnya yaitu dua angkarelatif prima14157 dan 5950.
Tapi kasus pengecualian harus teridentifikasi dan diuji.
Apakah "inelegan" berjalan benar saat R > S, S > R, R = S?
Sama juga dengan "Elegan": B > A, A > B, A = B?
(Semuanya benar).
Apa yang terjadi bila salah satu bilangan nol, atau keduanya nol?
("Inelegan" terus berjalan pada kedua kasus; "elegan" terus berjalan saat A = 0.)
Apa yang terjadi bila angkanegatifdimasukan?
Angka desimal?
Bila angka masukan, misalnyadomaindari fungsi yang dihitung oleh algoritma/program, mengikutkan hanya integer positif termasuk 0, maka kegagalan pada nol mengindikasikan bahwa algoritma (dan programinstansiasinya) adalah sebuahfungsi parsialbukannyafungsi total.
Kesalahan yang terkenal karena eksepsi adalah kegagalan roketAriane V.
Bukti dari kebenaran program menggunakan induksi matematika: Knuth mendemonstrasikan penggunaaninduksi matematikauntuk versi "pengembangan" dari algoritma Euclid, dan dia mengajukan "metode umum yang digunakan untuk membuktikan validitas dari setiap algoritma."Tausworthe mengajukan bahwa sebuah pengukuran dari kompleksitas dari sebuah program adalah panjang dari pembuktian kebenarannya.
Elegan (kepadatan) lawan kebaikan (kecepatan): Dengan hanya 6 instruksi dasar, "Elegan" adalah jelas pemenang dibandingkan dengan instruksi "inelegan" dengan 13 instruksi.
Namun, "inelegan" lebihcepat(ia sampai pada HALT dengan langkah lebih sedikit).Analisis algoritmamengindikasikan kenapa hal tersebut terjadi: "Elegan" melakukan pengujian kondisiduakali disetiap pengulangan pengurangan, sementara "inelegan" hanya sekali.
Bila algoritma (biasanya) membutuhkan banyak pengulangan,secara rata-ratalebih banyak waktu yang terbuang saat melakukan tes "B = 0?" yang hanya diperlukan saat sisa sudah dihitung.
Bisakah algoritma ditingkatkan?: Bila programmer sudah menilai sebuah program "cocok" dan "efektif"—yaitu, ia menghitung fungsi yang ditujukan oleh penulisnya—maka pertanyaannya menjadi, bisakah ditingkatkan?
Kepadatan dari "inelegan" bisa ditingkatkan dengan menghilangkan 5 langkah.
Tapi Chaitin membuktikan bahwa memadatkan algoritma tidak bisa diotomatiskan dengan algoritma generalisasi;tapi, ia bisa dilakukan secaraheuristik, misalnya dengan pencarian menyeluruh (contohnya bisa ditemukan diBerang sibuk), coba dan gagal, kecerdasan, kedalaman, penggunaanpenalaran induktif, dll.
Bisa diamati bahwa langkah 4, 5, dan 6 diulang pada langkah 11, 12, dan 13.
Pembandingan dengan "Elegan" menyediakan petunjuk langkah-langkah tersebut dengan langkah 2 dan 3 dapat dihilangkan.
Hal ini mereduksi jumlah instruksi dasar dari 13 menjadi 8, yang membuatnya "lebih elegan" dari "Elegan" dengan 9 langkah.
Kecepatan "Elegan" bisa ditingkatkan dengan memindahkan tes B=0? keluar dari pengulangan.
Perubahan ini memerlukan penambahan 3 instruksi (B=0?, A=0?, GOTO).
Sekarang "Elegant" menghitung contoh-angka lebih cepat;
untuk setiap angka pada A, B dan R, S hal ini selalu merupakan kasus yang membutuhkan analisis yang mendalam.
Sangat penting untuk mengetahui berapa banyak sumber tertentu (seperti waktu dan tempat penyimpanan) secara teoretis diperlukan untuk sebuah algoritma.
Metode-metode telah dikembangkan untukanalisis algoritmauntuk mendapatkan jawaban kuantitatif (estimasi);
sebagai contohnya, algoritma pengurutan di atas memerlukan waktu O(n), menggunakannotasi O besardengannsebagai panjang deret (yang akan diurut).
Setiap saat algoritma hanya perlu mengingat dua nilai: nilai terbesar yang ditemukan, dan posisinya sekarang dideretan input.
Oleh karena itu dikatakan memiliki kebutuhan ruangO(1), jika ruang yang dibutuhkan untuk menyimpan angka masukan tidak dihitung, atau O(n) jika dihitung.
Algoritma berbeda mungkin menyelesaikan pekerjaan yang sama dengan kumpulan instruksi yang berbeda dengan waktu, ruang, atau 'usaha' lebih sedikit atau banyak dari yang lain.
Sebagai contohnya, algoritmapencairan binaribiasanya mengungguli pencarian berderet secarapaksabila digunakan untuktabel pencarianpada deret terurut.
Analisis dan kajian algoritmaadalah bidang dari ilmu komputer, dan biasanya dilakukan secara abstrak tanpa menggunakanbahasa pemrogramantertentu atau implementasi.
Dalam artian, analisis algoritma mirip dengan bidang matematika lainnya yang mana fokus pada properti yang mendasari algoritma dan bukan pada implementasi tertentu.
Biasanyapseudokodedigunakan pada analisis karena merupakan representasi paling umum dan sederhana.
Namun, pada akhirnya, kebanyakan algoritma diimplementasikan di perangkat keras / lunak tertentu danefisiensi algoritmikmereka akhirnya diuji menggunakan kode yang sebenarnya.
Untuk solusi dari sebuah masalah, efisiensi dari algoritma tertentu mungkin tidak terlalu berpengaruh (kecuali n sangat besar) tetapi bagi algoritma yang dirancang untuk kecepatan interaktif, komersial, atau penggunaan ilmiah jangka panjang ia bisa saja kritikal.
Meningkatkan n dari kecil ke n yang besar biasanya menunjukan ketak efisienan algoritma yang tidak berbahaya.
Pengujian empiris berguna karena bisa membuka interaksi tak terduga yang mempengaruhi performa.Benchmarkbisa digunakan untuk membandingkan potensi kenaikan sebelum/sesudah algoritma setelah optimisasi program dilakukan.
Untuk menggambarkan kemungkinan potensi peningkatan bahkan pada algoritma yang sudah teruji, inovasi terbaru, berkaitan dengan algoritmaFFT(banyak digunakan di bidang pemrosesan gambar), bisa menurunkan waktu pemrosesan dengan faktor sampai 1.000 untuk aplikasi seperti pencitraan medis.Secara umum, peningkatan kecepatan bergantung pada properti khusus dari permasalahan, yang mana sangat umum pada aplikasi praktis.Percepatan dengan tingkat seperti itu membolehkan perangkat komputasi yang sering menggunakan pemrosesan gambar (seperti kamera digital dan peralatan medis) menghabiskan daya yang lebih sedikit.
Salah satu cara mengklasifikasikan algoritma yaitu dengan cara implementasi.
Cara lain mengklasifikasikan algoritma adalah dengan metodologi rancangannya atau paradigma.
Ada sejumlah paradigma, tiap-tiapnya berbeda dari yang lain.
Lebih lanjut, setiap kategori tersebut mengikutkan banyak tipe algoritma yang berbeda.
Beberapa paradigma umum termasuk:
Setiap bidang sains memiliki permasalahannya sendiri dan membutuhkan algoritma yang efisien. Masalah yang berkaitan di satu bidang terkadang dipelajari bersama. Beberapa contoh yaitualgoritma pencarian,algoritma penggabungan,algoritma numerik,algoritma grafik,algoritma deret,algoritma komputasi geometri,algoritma kombinatorial,algoritmas medis,mesin belajar,kriptografi, algoritmakompresi datadanteknik penguraian.
Terkadang bidang-bidang tersebut saling tumpang tindih, dan perkembangan algoritma di satu bidang bisa meningkatkan bidang lainnya yang terkadang tidak berkaitan. Sebagai contohnya, pemrograman dinamis ditemukan untuk optimisasi konsumsi sumber daya dalam industri, tetapi sekarang digunakan untuk menyelesaikan sejumlah besar permasalahan dalam banyak bidang.
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.
Burgin (2005, p. 24) menggunakan definisi algoritma secara umum yang melonggarkan kebutuhan bersama yang keluaran dari algoritma yang menjalankan sebuah fungsi harus ditentukan setelah sejumlah langkah. Dia mendefinisikan kelas super-rekursif dari algoritma sebagai "sebuah kelas algoritma yang mana memungkinkan untuk menghitung fungsi yang tidak bisa dihitung oleh mesin Turing manapun" (Burgin 2005, p. 107). Hal ini berkaitan dekat dengan kajian dari metodehiperkomputasi.
Untuk menjaga keseimbangan saat mengintegrasikan mesin ke dalam masyarakat, seseorang bisa mengklasifikasikan algoritma berdasarkan tipe dari evaluasi yang mereka lakukan.
Sejumlah filsuf telah berhipotesis bahwa masyarakat diuntungkan dari keragaman evaluatif seperti mereka diuntungkan keragaman jender dan tipe darah (misalnya, Dean 2012, Sober & Wilson 1998) Hertzke & McConkey 1998, dan Bellah 1985).
Teknologi dapat mengancam ekosistem moral tersebut seperispesies invasifjika ia mengganggu campuran keragaman.
Wallach & Allen (2008) mengklasifikasikan algoritma pembuat-keputusan menjadi tiga tipe evaluatif: Algoritma bottom-up membuat penilaian tidak terprediksi bagi pemrogram (misalnya, perangkat lunak yang berevolusi).
Yang lainnya (top-down) dibagi menjadideontologikal(yang dapat bergantung pada implementasi aturan pemrograman) lawanconsequensialis(yang mengandalkan pada memaksimalkan perkiraan pemrograman).
Sebagai contohnya, sebuah kalkulator standar termasuk deontologikal, sementaramesin pembelajaranuntuk perdagangan saham termasuk consequensialis.
Santos-Lang mengganti nama deontologikal dan consequensialis menjadi kelas "institusional" dan "negosiator" dengan tujuan untuk menghindari implikasi bahwa semua teori-teori etika deontologikal dan consequensialis bisa diimplementasikan sebagai algoritma, dan membagi kelas bottom-up menjadi "pengganggu" (algoritma yang tidak terprediksi karena menggunakan generator pengacakan) lawan "relasional" (algoritma yang tidak terprediksi karena efek jaringan).
Seorang mutator dalamkomputasi evolusionerbisa menjadi contoh dari pengganggu, sementara kelas 3 atau 4 dariotomata sellularadalah contoh dari mesin relasional.
Santos-Lang mencatat bahwa algoritma terkadang memiliki subkomponen dari tipe lainnya.
Sebagai contohnya, negosiator perdagangan saham bisa mengimplementasikan sebuah algoritma genetik, dan memiliki mutator pengganggu, dan mutator bisa memiliki subkomponen institusional dan relasional, semua komputasi adalah relasional pada tingkat di jajaran kimiawi (Santos-Lang 2014).
Kata sifat "berkelanjutan" bila diterapkan pada kata "algoritma" bisa berarti:
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 dalamGottschalk v. Benson).
Namun, penerapan praktis dari algoritma terkadang dipatenkan.
Sebagai contohnya, dalamDiamond v. Diehr, aplikasi dari algoritmaumpan-baliksederhana untuk membantu dalam menyembuhkankaret sintetisdianggap dapat dipatenkan.Mematenkan perangkat lunaksangat kontroversial, dan ada paten yang mengikutkan algoritma yang sangat dikritisi, terutama algoritmakompresi data, sepertiFormat GrafiknyaUnisys.
Sebagai tambahan, beberapa algoritma kriptografi memiliki batasan ekspor (lihatekspor dari kriptografi).
Kata"Algoritma", atau"Algorisma"pada versi penulisan lain, datang dari namaal-Khwarizmi. dieja dalam Arab klasik sebagai Al-Khwarithmi. Al-khwarizmi (bahasa Persia:خوارزمي, 780-850) adalahmatematikawan,ahli astronomi,ahli geografidariPersiadan sarjanaBaitul HikmahdiBaghdad, yang arti namanya"penduduk asliKhwarezmia", sebuah kota yang merupakan bagian dariWilayah Iranpada masanya dan sekarangUzbekistan.Sekitar tahun 825, dia menulis risalah dalam bahasa Arab, yang diterjemahkan dalamLatinpada abad ke-12 dengan judulAlgoritmi de numero Indorum.
Judul ini artinya "Algoritmi pada bilangan India", di mana "Algoritmi" adalah pelatinan penerjemah dari nama Al-Khwarizmi.Al-Khwarizmi dulunya adalah matematikawan yang paling banyak dibaca di Eropa pada akhir Abad Pertengahan, pada umum lewat bukunya yang lain,Aljabar.Pada akhir abad pertengahan,algorismus, perubahan dari namanya, berarti "sistem bilangan desimal" yang masih merupakan arti dari kata Inggris modernalgorism.
Pada abad ke-17 Prancis kata tersebut berubah, tetapi tidak maknanya, menjadialgorithme.
Inggris mengadopsi Prancis setelahnya, tetapi tidak pada akhir abad ke-19 lah "Algorithm" mengambil makna dari kata Inggris masa sekarang.
Etimologi alternatif mengklaim asal mulanya dari istilahalgebra(aljabar) dari makna abad pertengahan "aritmetika Arab" danarithmosistilah Yunani untuk angka (yang secara harfiah berarti "bilangan Arab" atau "perhitungan Arab").
Karya algoritma Al-Kharizmi bukan berbentuk seperti pada masa modern sekarang tetapi sebagai tipe dari pengulangan kalkulus (disini disebutkan bahwa karya fundamentalnya yang dikenal sebagaialgebrapada awalnya berjudul "Buku Ringkasan tentang Kalkulasi dengan Penyempurnaan dan Pengimbangan" menjelaskan tipe-tipe dari pengulangan perhitungan danpersamaan kuadrat).
Dalam makna tersebut, algoritima dikenal di Eropa jauh sebelum Al-Kharizmi.
Algoritma paling tua yang dikenal sekarang adalahAlgoritma Euklid(lihat jugaPengembangan algoritma Euklid).
Sebelum ditemukan istilahalgorithmorang Yunani menyebutnyaanthyphairesissecara harfiah berarti anti-substraksi atau substraksi timbal-balik (untuk bacaan lebih lanjutdisinidaniniDiarsipkan2013-11-03 diWayback Machine..
Algoritma dikenal oleh orang Yunani berabad sebelumEuclid.
Bukannya kataalgebraorang Yunani menggunakan istilaharithmetica(ἀριθμητική, yaitu dalam karyaDiophantusyang dikenal "bapak dari Aljabar" - lihat juga artikel Wikipediapersamaan DiophantinedanEudoxos).
Bukti terawal tentang algoritma ditemukan dalam matematikaBabiloniadiMesopotamiakuno (saat ini merupakan bagian dariIrak). Sebuah tablet tanah liatSumeriayang ditemukan di Shuruppak dekatBaghdaddan berasal dari sekitar tahun 2500 SM menjelaskan algoritma divisi yang paling awal.Selama dinasti Hammurabi sekitar 1800-1600 SM, tablet tanah liat Babilonia menjabarkan algoritma untuk rumus-rumus komputasi.Algoritma juga digunakan dalam astronomi Babilonia. Tablet tanah liat Babilonia menguraikan dan menggunakan prosedur algoritmik untuk menghitung waktu dan tempat peristiwa astronomi yang signifikan.
Algoritma untuk aritmatika juga ditemukan dalam matematika Mesir kuno, yang terdapat pada Papirus Matematika Rhind yang berasar dari sekitar tahun 1550 SM.Algoritma kemudian digunakan dalam matematikaHelenistikkuno. Dua contohnya adalahTapis Eratosthenes, yang dijelaskan dalam Pengenalan Aritmatika olehNicomachus,danAlgoritma Euklides, yang pertama kali dipaparkan dalam Euclid's Elements (sekitar 300 SM).
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 akhirnyabilangan Romadanabakusberkembang (Dilson, p. 16-41).
Penanda penghitung muncul dalamsistem bilangan operanaritmetika digunakan dalammesin Turingdan komputasimesin Post-Turing.
Karya dariGeometer Yunanikuno (algoritma Euklid),matematikawan IndiaBrahmagupta, danmatematikawan PersiaAl-Khwarizmi(yang darinya isitlah "algorism" dan "algoritma" diturunkan), dan matematikawan Eropa Barat memuncak dalam notasiLeibnizdarirasiosinator kalkulus(sekitar 1680-an):
Jam: Bolter memuji penemuanjamgaya-berat sebagai "Kunci penemuandari Eropa pada Abad Pertengahan", khususnya padaambang pelarianyang menyediakan kita dengan tik dan tak dari jam mekanis.
"Mesin otomatis yang akurat"mengarah langsung pada "otomatamekanis" dimulai pada abad ke-13 dan terakhir pada "mesin komputasi" --motor berbedadanmotor analitikdariCharles Babbagedan bangsawanAda Lovelace, pertengahan abad ke-19.Lovelace dikreditkan sebagai yang pertama menciptakan algoritma yang ditujukan untuk diproses di komputer—motor analitis Babbage, perangkat pertama yang dianggapkomputerTuring-sempurnasebenarnya bukan hanya sebuahkalkulator—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 mereduksipersamaan booleanbila ditampilkan dalam sebuah bentuk yang pada masa sekarang dikenal sebagaipemetaan Karnaugh.
Jevons (1880) pertama menjelaskan "sempoa" sederhana dari "potongan kayu dilengkapi dengan penyemat, dibuat supaya bagian atau kelas kombinasilogikamanapun 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 sebuahMesin 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 "silogismeatau argumen logika sederhana apapun".
Mesin tenun Jacquard, kartu berlobangnya Hollerith, telegraf dan telepon -- penyiaran elektromekanis: Bell dan Newell (1971) mengindikasikan bahwamesin tenun Jacquard(1801), pelopor darikartu Hollerith(kartu berlobang, 1887), dan "teknologi alih telepon" adalah akar dari sebuah pohon yang mengarah pada perkembangan dari komputer pertama.Pada pertengahan abad ke-19telegraf, pelopor dari telepon, digunakan diseluruh dunia, pengkodean diskrit dan pembedaan huruf sebagai "titik dan strip".
Pada akhir abad ke-19pita telegraf(sekitar 1870-an) digunakan, sebagaimana juga kartu Hollerith pada sensus Amerika 1890.
Kemudian muncullahteleprinter(sekitar 1910-an) dengan kerta-berlobang menggunakankode Baudotdi pita.
Jaringan alih-telepondaripenyiaranelektromekanis (ditemukan 1835) adalah karya dairGeorge 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".
Davis (2000) mengamati pentingnya penyiaran elektromekanis (dengan "keadaan binari"-nyabukadantutup):
Simbol dan aturan: Dengan cepat berkembangnya matematika dariGeorge Boole(1847, 1854),Gottlob Frege(1897), danGiuseppe 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".
Tapi Heijenoort memberi pujian pada Frege (1879): Frege "merupakan karya tulis paling penting mengenai logika. ... yang mana kita lihat sebuah "'bahasa formula', yaitu sebuahlingua 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".Karya dari Frege lebih lanjut disederhanakan dan diperkuat olehAlfred North WhiteheaddanBertrand RusselldalamPrincipia Mathematical(1910-1913).
Paradoks: Pada masa yang sama sejumlah paradoks yang mengganggu muncul dalam literatur, pada khususnyaparadoks Burali-Forti(1987),paradoks Russell(1902-03), danParadoks Richard.Hasilnya mengarah ke makalahKurt Godel(1931) -- dia secara khusus merujuk paradoks pembohong—yang mereduksi aturan darirekursipada angka.
Penghitungan Efektif: Dalam usaha untuk menyelesaikanpermasalahan keputusanyang 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-λolehAlonzo Church,Stephen Kleene, danJ.B. Rosserdefinisi dari "rekursi umum" yang benar-benar diasah dari karya Godel berdasarkan saran dariJacquard Herbrand(cf. kuliah Godel di Princeton tahun 1934) dan penyederhaan selanjutnya oleh Kleene.Church membuktikanbahwa permasalahan keputusan tidak terpecahkan, definisiEmil Posttentang 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]"-nyadengan efek yang mirip dengan "formulasi"-nya Post, definisiJ. Barkley Rossertentang "metode efektif" dalam makna "sebuah mesin".ProposalS. C. Kleenedari pelopor "Tesis Church" yang disebutnya "Thesis I",dan beberapa tahun kemudian Kleene menamakan tesisnya "Tesis Church"dan mengajukan "Tesis Turing".
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:
Simbol ruangnya yaitu
Turing—model dari komputasinya sekarang dikenal denganmesin 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.
Reduksi Turing menghasilkan hal berikut:
"Bisa saja beberapa dari perubahan tersebut menyebabkan perubahan keadaan pikiran. Operasi tunggal paling umum oleh karena itu harus diambil jadi salah satu hal berikut:
Beberapa tahun kemudian, Turing mengembangkan analisisnya (tesis, secara definisi) dengan ekspresi kuat berikut:
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. Barkley Rossermendefinisikan 'metode [matematis] efektif' dengan cara berikut (kemiringan ditambahkan):
Catatan kaki Rosser #5 merujuk karya dari (1) Church dan Kleene dan definisi dari definabiliti-λ, secara khusus Church menggunakannya dalamAn Unsolvable Problem of Elementary Number Theory-nya (1936);
(2) Herbrand dan Godel dan penggunaan rekursi mereka terutama Godel menggunakannya dalam makalah terkenalnyaOn 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. Kleenedidefinisikan sebagai "Thesis I"-nya yang terkenal yang dikenal sebagaitesis Church-Turing.
Tapi dia melakukan hal tersebut dalam konteks berikut (penebalan dari aslinya):
Sejumlah usaha telah diarahkan untuk memperbaiki lebih lanjut definisi dari "algoritma", dan aktivitas tersebut masih terus berjalan karena isu-isu yang mengelilinginya, terutama,fondasi matematika(khususnyatesis Church-Turing) danfilsafat pikiran(khususnya argumen menyangkutkecerdasan buatan).
Lebih lanjut, lihatkarakterisasi algoritma.