Jabarkan Formalisasi dari Algoritma

Algoritme sangat penting bagi cara komputer mengolah data.

Banyak program komputer mengandung algoritme 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 algoritme bisa dianggap sebagai urutan operasi yang bisa disimulasikan oleh sebuah sistem Turing-lengkap.

Penulis yang mendukung tesis ini termasuk Minsky (1967), Savage (1987), dan Gurevich (2000):

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

Walaupun tampaknya ekstrem, alasan tersebut ... sukar disanggah".

Gurevich: "... argumen informal Turing untuk menyokong tesis ini membenarkan tesis yang lebih kuat: setiap algoritme bisa disimulasikan oleh sebuah mesin Turing ... menurut Savage [1987], sebuah algoritme adalah sebuah proses penghitungan yang ditentukan oleh sebuah mesin Turing".

Biasanya, bila sebuah algoritme 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 algoritme.

Pada praktiknya, keadaan tersebut disimpan pada satu atau lebih struktur data.

Untuk beberapa proses komputasi, algoritme 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 algoritme adalah kumpulan dari langkah-langkah yang tepat, urutan dari komputasi selalu penting bagi berfungsinya algoritme.

Instruksi biasanya diasumsikan terdaftar secara eksplisit, dan dijelaskan dimulai "dari atas" dan terus "ke bawah", sebuah gambaran yang dijelaskan secara formal oleh alur kontrol

Sejauh ini, diskusi tentang formalisasi algoritme telah mengasumsikan premis dari pemrograman imperatif.

Hal ini merupakan konsepsi umum, yang mencoba menjelaskan sebuah pekerjaan dalam makna diskrit dan "mekanis".

Keunikan dari konsepsi formalisasi algoritme adalah operasi 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 algoritme lihat pemrograman fungsional dan pemrograman logika.