Otomata Church Turing oleh Nadin Nabil Hafizh Ayyasy

Church Turing

Oleh :

Nadin Nabil Hafizh Ayyasy (5025231061)

Dosen:

Ilham Gurat Adillion, S.Kom., M.Eng.

INSTITUT TEKNOLOGI SEPULUH NOPEMBER SURABAYA 

2025/2026

BAB I

Pendahuluan

1.1 Latar Belakang

Dimulai dengan pertanyaan ambisius dari matematikawan David Hilbert yang dikenal sebagai Entscheidungsproblem (Masalah Keputusan). Hilbert mempertanyakan apakah ada sebuah "prosedur mekanis" atau algoritma universal yang mampu menentukan kebenaran atau kesalahan dari setiap pernyataan matematika. Masalah utama untuk menjawab pertanyaan ini adalah tidak adanya definisi matematis yang formal untuk "prosedur mekanis" itu sendiri; konsep tersebut masih bersifat intuitif.

Untuk mengatasi kekosongan definisi ini, pada pertengahan tahun 1930-an, dua pemikir brilian secara independen mengembangkan model komputasi formal mereka. Di Amerika Serikat, ahli logika Alonzo Church menciptakan Kalkulus Lambda (λ-calculus), sebuah sistem berbasis fungsi untuk merepresentasikan komputasi. Sementara itu, di Inggris, Alan Turing merancang Mesin Turing, sebuah model mesin abstrak yang meniru cara manusia melakukan perhitungan langkah demi langkah secara mekanis. Keduanya, dengan menggunakan model masing-masing, berhasil membuktikan bahwa jawaban untuk Entscheidungsproblem adalah "tidak"—tidak ada algoritma universal semacam itu.

Momen puncaknya adalah penemuan bahwa model Kalkulus Lambda milik Church dan Mesin Turing milik Turing, meskipun dikembangkan secara terpisah dan memiliki bentuk yang sangat berbeda, ternyata ekuivalen secara komputasi. Artinya, keduanya memiliki kekuatan yang sama dalam menyelesaikan masalah. Kesetaraan yang kuat ini memberikan keyakinan bahwa esensi sejati dari "komputasi" telah berhasil ditangkap. Dari sinilah Tesis Church-Turing dirumuskan: sebuah prinsip yang menyatakan bahwa Mesin Turing secara akurat mencakup setiap proses yang dapat kita sebut sebagai komputasi algoritmik. Tesis ini tidak hanya menetapkan batas teoretis dari apa yang dapat dihitung, tetapi juga menjadi landasan bagi ilmu komputer modern.

1.2 Rumusan Masalah

Berikut Adalah rumusan masalah dari dibuatnya makalah ini :

1. Apa itu church turing ?

2. Bagaimana sejarah pengembangannya ?

3. Apa saja jenis-jenis turing machine ?

4. Apa saja manfaat mengetahui turing machine ?

5. Apa contoh bahasa pemrograman dari masing-masing jenis turing machine dan apa alasannya ?

BAB II

Pembahasan

2.1 Definisi Church Turing

Dalam teori komputabilitas, Tesis Church–Turing (juga dikenal sebagai tesis komputabilitas, tesis Turing–Church, konjektur Church–Turing, tesis Church, konjektur Church, dan tesis Turing) adalah sebuah dalil (tesis) mengenai hakikat fungsi yang dapat dihitung (computable functions). Tesis ini menyatakan bahwa sebuah fungsi pada bilangan asli dapat dihitung melalui metode yang efektif jika dan hanya jika fungsi tersebut dapat dihitung oleh sebuah Mesin Turing. Tesis ini dinamai berdasarkan nama matematikawan Amerika, Alonzo Church, dan matematikawan Inggris, Alan Turing.

Pada tahun 1930-an, para matematikawan berupaya memberikan definisi formal untuk konsep intuitif "dapat dihitung secara efektif". Upaya ini menghasilkan tiga model komputasi yang dikembangkan secara independen: fungsi rekursif umum oleh Kurt Gödel, kalkulus lambda (λ-calculus) oleh Alonzo Church, dan Mesin Turing oleh Alan Turing. Masing-masing model ini menawarkan cara yang presisi untuk mendefinisikan apa artinya sebuah fungsi dapat dihitung.

Terobosan fundamental terjadi ketika terbukti bahwa ketiga pendekatan yang berbeda ini ternyata ekuivalen secara komputasi; apa pun yang bisa dihitung oleh satu model, bisa juga dihitung oleh model lainnya. Kesetaraan ini memperkuat keyakinan bahwa para ilmuwan telah secara akurat menangkap esensi dari komputabilitas.

Hal ini mengarah pada Tesis Church-Turing, yang menyatakan bahwa gagasan informal tentang "metode efektif" setara dengan model-model formal ini. Meskipun diterima secara luas, tesis ini tidak dapat dibuktikan secara matematis karena menghubungkan konsep intuitif dengan definisi formal. Sejak saat itu, berbagai variasi tesis telah muncul, yang memperluas gagasannya ke bidang fisika dan teori kompleksitas.

2.2 Sejarah Church Turing

Sejarah Tesis Church-Turing berakar pada salah satu masalah paling penting bagi para ahli logika pada tahun 1930-an, yaitu Entscheidungsproblem (Masalah Keputusan) yang diajukan oleh David Hilbert dan Wilhelm Ackermann. Masalah ini menuntut adanya sebuah "prosedur mekanis" untuk membedakan kebenaran dan kesalahan dalam matematika. Namun, tantangan utamanya adalah belum adanya definisi formal untuk "algoritma" atau "kalkulasi efektif". Hal ini memicu perdebatan filosofis: apakah konsep ini seharusnya menjadi sebuah aksioma, definisi, hipotesis empiris, atau sekadar sebuah proposal (tesis).

Pada awalnya, Alonzo Church dan muridnya, Stephen Kleene, memperkenalkan fungsi terdefinisi-lambda (λ-definable) dan mengusulkan bahwa inilah definisi formal dari "kalkulasi efektif". Namun, Kurt Gödel tidak yakin dan menganggap usulan tersebut "sangat tidak memuaskan". Gödel lebih menyarankan pendekatan aksiomatik untuk mendefinisikan konsep tersebut, meskipun ia tidak pernah mengembangkannya lebih lanjut.

Perkembangan penting terjadi ketika Alan Turing memperkenalkan model mesin teoritisnya, yang kini dikenal sebagai Mesin Turing. Di sisi lain, Emil Post secara independen juga mengembangkan gagasan serupa dan berpendapat bahwa "identifikasi" kalkulasi efektif dengan sistem formal tertentu bukanlah sebuah definisi, melainkan sebuah "hipotesis kerja" yang validitasnya perlu terus diuji dan mungkin akan mengarah pada sebuah "hukum alam".

Titik baliknya adalah ketika terbukti bahwa ketiga pendekatan—fungsi rekursif (yang dikembangkan dari ide Gödel), kalkulus lambda Church, dan Mesin Turing—ternyata ekuivalen secara komputasi. J. Barkley Rosser pada tahun 1939 secara formal menyatakan kesetaraan ketiga definisi tersebut. Namun, istilah "tesis" secara eksplisit baru diperkenalkan oleh Stephen Kleene pada tahun 1943. Ia mengajukan "Thesis I" yang menyatakan bahwa setiap fungsi yang dapat dihitung secara efektif adalah fungsi rekursif umum, dan menegaskan bahwa ini adalah inti dari usulan Church dan Turing. Kleene jugalah yang kemudian memformalkan dan mempopulerkan nama "Tesis Church-Turing".

Diskusi mengenai hakikat tesis ini terus berlanjut. Pada dekade-dekade berikutnya, para peneliti seperti Robin Gandy (murid Turing) dan Wilfried Sieg mencoba memperdalam pemahaman dengan menganalisis batasan fisik mesin dan aksioma yang mendasari kerja seorang penghitung (manusia). Pada akhirnya, banyak kalangan kini memandang tesis ini sebagai sebuah definisi yang kuat dan teruji, setara dengan definisi fundamental lainnya dalam matematika, seperti definisi fungsi kontinu.

2.2 Turing Equivalent dan Turing Complete

Sebuah sistem komputasi disebut Turing complete jika dapat digunakan untuk mensimulasikan mesin Turing universal. Dengan kata lain, jika sebuah sistem dapat menyelesaikan masalah komputasi apa pun yang dapat diselesaikan oleh mesin Turing (dengan cukup yang waktu dan memori yang cukup), maka sistem tersebut dianggap Turing complete. Dimana berarti sistem tersebut secara teoritis setara dengan komputer paling kuat yang bisa kita bayangkan.

Turing equivalent adalah istilah yang digunakan untuk menggambarkan dua atau lebih sistem komputasi yang memiliki kekuatan komputasi yang sama. Jika sistem A dapat mensimulasikan sistem B, dan sebaliknya sistem B dapat mensimulasikan sistem A, maka keduanya disebut Turing equivalent. Pada dasarnya, semua sistem yang Turing complete juga Turing equivalent satu sama lain.

2.2.1 Manfaat Mengetahui Turing Equivalent dan Turing Complete

Memahami konsep ini memberikan beberapa manfaat krusial, baik dari sisi teoritis maupun praktis:

1. Batas Kemampuan Komputasi : Konsep ini membantu kita memahami batas fundamental dari apa yang mungkin untuk dihitung. Masalah-masalah yang tidak dapat diselesaikan oleh mesin Turing (seperti Halting Problem) juga tidak akan dapat diselesaikan oleh bahasa pemrograman atau sistem komputasi apa pun, secanggih apa pun itu.

2. Evaluasi Bahasa Pemrograman : Mengetahui apakah sebuah bahasa pemrograman Turing complete adalah cara cepat untuk memahami kemampuannya. Jika sebuah bahasa Turing complete, itu berarti bahasa tersebut cukup kuat untuk mengekspresikan algoritma kompleks apa pun.

3. Interoperabilitas : Karena semua sistem yang Turing complete pada dasarnya setara, ini menyiratkan bahwa program yang ditulis dalam satu bahasa Turing complete secara teoritis dapat ditulis ulang dalam bahasa Turing complete lainnya.

2.2.1 Contoh Bahasa Turing Equivalent

Hampir semua bahasa pemrograman modern yang serbaguna (general-purpose) adalah Turing complete. Ini adalah syarat agar mereka dapat digunakan untuk mengembangkan perangkat lunak yang kompleks.

Contoh: Python

Python dianggap Turing complete karena ia memiliki semua komponen yang diperlukan untuk menyimulasikan mesin Turing. Alasan utamanya adalah kemampuannya untuk melakukan looping tak terbatas (atau kondisional) dan mengakses memori tak terbatas (secara teoritis).

• Looping Kondisional: Python memiliki konstruksi seperti while loop. Sebuah while True: loop, misalnya, dapat terus berjalan selamanya sampai sebuah kondisi break terpenuhi. Kemampuan untuk mengulang instruksi secara tak terbatas ini adalah inti dari simulasi mesin Turing yang dapat terus memproses "pita" datanya.

• Akses Memori: Python dapat secara dinamis meminta lebih banyak memori dari sistem operasi. Meskipun dalam praktiknya memori fisik terbatas, model abstraksi bahasa Python memungkinkan programmer untuk bertindak seolah-olah memori tidak terbatas, sama seperti pita tak terbatas pada mesin Turing.

Kombinasi dari kemampuan untuk membuat keputusan (dengan if-else), melakukan perulangan (dengan for atau while), dan menyimpan serta memanipulasi data dalam memori membuat Python mampu menjalankan algoritma apa pun yang bisa dijalankan oleh mesin Turing.

2.2.1 Contoh Bahasa Turing Complete

Bahasa atau sistem yang tidak Turing complete seringkali dirancang untuk tujuan yang lebih spesifik dan terbatas, di mana keamanan dan prediktabilitas lebih penting daripada kekuatan komputasi universal.

Contoh: HTML (HyperText Markup Language)

HTML bukan bahasa yang Turing complete. HTML adalah bahasa markah (markup language), bukan bahasa pemrograman. Tugas utamanya adalah untuk menstrukturkan dan menampilkan konten di halaman web, bukan untuk melakukan komputasi.Berikut alasan mengapa HTML tidak Turing complete adalah:

• Tidak Adanya Logika Kondisional: HTML tidak memiliki cara untuk membuat keputusan. Tidak ada padanan if-else untuk mengubah perilaku berdasarkan input atau kondisi tertentu.

• Tidak Adanya Perulangan (Looping): HTML tidak dapat menjalankan serangkaian instruksi berulang kali. Ia hanya memproses dokumen dari atas ke bawah satu kali dan menampilkannya.

• Tidak Ada Manipulasi State/Memori: HTML tidak memiliki variabel atau cara untuk menyimpan dan memodifikasi data selama "eksekusi". Ia adalah representasi statis dari sebuah struktur.

Karena keterbatasan ini, mustahil untuk menulis program kompleks seperti kalkulator atau game hanya dengan menggunakan HTML. HTML membutuhkan bahasa lain yang Turing complete (seperti JavaScript) untuk menambahkan logika dan interaktivitas.

2.2 Kesimpulan

Berdasarkan pembahasan yang telah diuraikan, dapat ditarik beberapa kesimpulan utama sebagai berikut:

1. Tesis Church-Turing adalah Fondasi Ilmu Komputer : Tesis ini secara fundamental menyatakan bahwa setiap masalah yang dapat dihitung secara intuitif oleh "prosedur mekanis" atau algoritma, juga dapat diselesaikan oleh sebuah Mesin Turing. Meskipun tidak dapat dibuktikan secara matematis, kesetaraan antara model Mesin Turing, Kalkulus Lambda, dan fungsi rekursif memberikan keyakinan kuat bahwa tesis ini berhasil menangkap esensi sejati dari komputabilitas.

2. Lahir dari Kebutuhan Akan Definisi Formal : Sejarah Tesis Church-Turing tidak dapat dipisahkan dari Entscheidungsproblem David Hilbert. Upaya untuk menjawab pertanyaan tersebut mendorong para pemikir seperti Alan Turing dan Alonzo Church untuk menciptakan model komputasi formal, yang pada akhirnya mendefinisikan batas-batas dari apa yang mungkin dan tidak mungkin untuk dihitung.

3. Turing Complete sebagai Ukuran Kekuatan Komputasi : Sebuah bahasa pemrograman atau sistem komputasi disebut Turing complete jika ia memiliki kekuatan komputasi yang setara dengan Mesin Turing universal. Ini berarti sistem tersebut, secara teoritis, mampu menjalankan algoritma apa pun. Kemampuan ini dicirikan oleh adanya kontrol alur (seperti looping tak terbatas) dan akses ke memori.

4. Hampir Semua Bahasa Pemrograman Modern adalah Turing Complete : Bahasa seperti Python, Java, C++, dan lainnya dirancang untuk menjadi Turing complete agar dapat digunakan untuk membangun perangkat lunak yang kompleks. Sebaliknya, bahasa yang tidak Turing complete, seperti HTML atau SQL (dalam bentuk dasarnya), dirancang untuk tujuan spesifik (menstrukturkan data atau kueri) dan sengaja dibatasi untuk menjamin prediktabilitas dan keamanan.

5. Manfaat Praktis dan Teoritis : Memahami konsep Turing complete membantu kita mengenali batas teoretis komputasi (misalnya, Halting Problem), mengevaluasi kemampuan sebuah bahasa pemrograman, dan memahami prinsip interoperabilitas antar sistem komputasi yang berbeda.

Daftar Pustaka

Copeland, B. J. (Ed.). (2004). The Essential Turing: Seminal Writings in Computing, Logic, Philosophy, Artificial Intelligence, and Artificial Life plus The Secrets of Enigma. Oxford University Press.

Davis, M. (Ed.). (1965). The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions. Raven Press.

Sipser, M. (2012). Introduction to the Theory of Computation (3rd ed.). Cengage Learning.

Hodges, A. (2012). Alan Turing: The Enigma. Princeton University Press.

Petzold, C. (2008). The Annotated Turing: A Guided Tour Through Alan Turing's Historic Paper on Computability and the Turing Machine. Wiley Publishing.

Church, A. (1936). "An Unsolvable Problem of Elementary Number Theory". American Journal of Mathematics, 58(2), 345–363.

Turing, A. M. (1936). "On Computable Numbers, with an Application to the Entscheidungsproblem". Proceedings of the London Mathematical Society, s2-42(1), 230–265.

Soare, Robert I. (2009-09-01). "Turing oracle machines, online computing, and three displacements in computability theory". Annals of Pure and Applied Logic. Computation and Logic in the Real World: CiE 2007. 160 (3): 368–399.

Conrad, Michael (May 1985). "On design principles for a molecular computer". Communications of the ACM. 28 (5): 464–480.

Proceedings of the London Mathematical Society on 28 May 1936, read on 12 November 1936, and published in series 2, volume 42 (1936–1937); it appeared in two sections: in Part 3 (pages 230–240), issued on 30 November 1936 and in Part 4 (pages 241–265), issued on 23 December 1936; Turing added corrections in volume 43 (1937), pp. 544–546.

Church, A. (1936). "An Unsolvable Problem of Elementary Number Theory". American Journal of Mathematics, 58(2), 345–363.

Davis, M. (Ed.). (1965). The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions. Raven Press. (Buku ini memuat banyak paper asli, termasuk dari Gödel, Church, Turing, dan Post).

Gandy, R. (1980). "Church's Thesis and Principles for Mechanisms". Dalam The Kleene Symposium (pp. 123–148). North-Holland.

Hilbert, D., & Ackermann, W. (1928). Grundzüge der theoretischen Logik. Springer.

Kleene, S. C. (1943). "Recursive Predicates and Quantifiers". Transactions of the American Mathematical Society, 53(1), 41–73.

Kleene, S. C. (1952). Introduction to Metamathematics. Van Nostrand. (Buku di mana Kleene secara formal membahas "Church's Thesis" dan "Turing's Thesis").

Post, E. L. (1936). "Finite Combinatory Processes—Formulation 1". The Journal of Symbolic Logic, 1(3), 103–105.

Rosser, J. B. (1939). "An Informal Exposition of Proofs of Gödel's Theorems and Church's Theorem". The Journal of Symbolic Logic, 4(2), 53–60.

Sieg, W. (2002). "Calculations by Man and Machine: Conceptual Analysis". Dalam Reflections on the Foundations of Mathematics: Essays in Honor of Solomon Feferman (pp. 390–409). Association for Symbolic Logic.

Soare, R. I. (1996). "Computability and Recursion". Bulletin of Symbolic Logic, 2(3), 284–321.

Turing, A. M. (1937). "On Computable Numbers, with an Application to the Entscheidungsproblem". Proceedings of the London Mathematical Society, s2-42(1), 230–265.

Sipser, M. (2012). Introduction to the Theory of Computation. Cengage Learning.

Turing, A. M. (1937). On Computable Numbers, with an Application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, s2-42(1), 230–265.

Hopcroft, J. E., Motwani, R., & Ullman, J. D. (2006). Introduction to Automata Theory, Languages, and Computation. Addison-Wesley.

Godel, K. (1931). Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I. Monatshefte für Mathematik und Physik, 38(1), 173-198.