Church-Turing Thesis telah menjadi subjek dari banyak variasi dan interpretasi selama bertahun-tahun. Secara khusus, ada versi yang hanya merujuk pada fungsi atas bilangan asli (seperti yang dilakukan Church dan Kleene), sementara yang lain merujuk pada fungsi (seperti yang dimaksudkan Turing) (Boker and Dershowitz). Salah satu rumusan yang umum adalah bahwa setiap komputasi yang efektif dapat dilakukan oleh mesin Turing (yaitu, oleh mesin komputasi abstrak Turing, yang dalam bentuk universalnya merangkum prinsip-prinsip logika mendasar dari komputer digital serba guna dengan program tersimpan). Penafsiran ulang modern dari tesis Church-Turing mengubahnya, memperluasnya ke fisika fundamental, teori kompleksitas, algoritma eksotis, dan ilmu kognitif. Namun, penting untuk menyadari bahwa beberapa tesis yang saat ini disebut sebagai tesis Church-Turing paling tinggi merupakan kerabat yang sangat jauh dari tesis yang diajukan oleh Church dan Turing (Hewitt).

Makalah Turing yang terkenal tahun 1936 mengembangkan model Mesin Turing (TM) dan menunjukkan bahwa TM memiliki ekspresi algoritma (yang sekarang dikenal sebagai Tesis Church-Turing). Tesis Church-Turing: Setiap kali ada metode (algoritma) yang efektif untuk memperoleh nilai fungsi matematika, fungsi tersebut dapat dihitung oleh TM. TM diidentifikasi dengan gagasan efektivitas; komputabilitas adalah istilah terkini untuk gagasan yang sama. Secara khusus, TM menangkap fungsi yang dapat dihitung sebagai transformasi efektif dari string terbatas (bilangan asli) ke string terbatas (Goldin and Wegner).

1.2 Rumusan Masalah

1. Apa yang dimaksud dengan Church-Turing Thesis dan bagaimana konsep dasarnya dikembangkan?

2. Apa pengertian dari Turing Complete dan Turing Equivalent, serta bagaimana kaitannya dengan mesin Turing?

3. Apa manfaat mengetahui Turing Complete dan Turing Equivalent?

4. Apa saja contoh bahasa pemrograman yang bersifat Turing Complete dan apa karakteristiknya?

5. Apa contoh bahasa yang tidak Turing Complete, dan mengapa bahasa tersebut memiliki keterbatasan dalam komputasi?

1.3 Tujuan

1. Mengetahui lebih dalam mengenai Church-Turing Thesis dan konsep dasar yang dikembangkan

2. Mengetahui pengertian mengenai Turing Complete dan Turing Equivalent serta kaitannya dengan Turing Machine atau mesin Turing

3. Mengetahui manfaat dari Turing Complete dan Turing Equivalent

4. Mengetahui beberapa bahasa pemrograman yang bersifat Turing Complete dan karakteristik yang membedakannya

5. Mengetahui beberapa bahasa pemrograman yang tidak bersifat Turing Complete dan alasan keterbatasan dalam komputasi

BAB II

PEMBAHASAN

2.1 Dasar Teori

2.1.1 Chuch-Turing

Dalam teori komputabilitas, tesis Church–Turing (juga dikenal sebagai tesis komputabilitas, tesis Turing–Church, dugaan Church–Turing, tesis Church, dugaan Church, dan tesis Turing) adalah tesis tentang sifat fungsi komputasi. Dinyatakan bahwa fungsi pada bilangan asli dapat dihitung dengan metode efektif jika dan hanya jika dapat dihitung dengan mesin Turing. Tesis ini dinamai menurut matematikawan Amerika Alonzo Church dan matematikawan Inggris Alan Turing. Sebelum definisi fungsi komputasi yang tepat, matematikawan sering menggunakan istilah informal yang dapat dihitung secara efektif untuk menggambarkan fungsi yang dapat dihitung dengan metode kertas dan pensil (“Church–Turing thesis - Wikipedia”).

Tesis Church-Turing membahas konsep metode yang efektif atau sistematis atau mekanis, seperti yang digunakan dalam logika, matematika, dan ilmu komputer. "Efektif" dan sinonimnya "sistematis" dan "mekanis" adalah istilah seni dalam disiplin ilmu ini: keduanya tidak memiliki makna sehari-hari. Suatu metode, atau prosedur, M, untuk mencapai suatu hasil yang diinginkan disebut "efektif" (atau "sistematis" atau "mekanis") hanya jika:

M, ditetapkan dalam bentuk sejumlah instruksi pasti yang terbatas (setiap instruksi dinyatakan dengan sejumlah simbol yang terbatas)
M, akan, jika dilakukan tanpa kesalahan, menghasilkan hasil yang diinginkan dalam sejumlah langkah yang terbatas;
M, dapat (dalam praktik atau prinsip) dilakukan oleh manusia tanpa bantuan mesin apa pun kecuali kertas dan pensil;
M, tidak menuntut wawasan, intuisi, atau kecerdikan, dari pihak manusia yang melakukan metode tersebut.

Contoh terkenal dari metode yang efektif adalah uji tabel kebenaran untuk tautologi. Pada prinsipnya, manusia yang bekerja dengan hafalan dapat menerapkan uji ini dengan sukses pada rumus kalkulus proposisional apa pun—dengan waktu, keuletan, kertas, dan pensil yang cukup (meskipun dalam praktiknya, uji ini tidak dapat diterapkan pada rumus apa pun yang mengandung lebih dari beberapa variabel proposisional) (Hewitt).

2.1.2 Turing Complete

Turing Complete adalah bahasa yang dapat melakukan komputasi apa pun. Tesis Church-Turing menyatakan bahwa komputasi yang dapat dilakukan dapat dilakukan oleh mesin Turing. Mesin Turing adalah mesin dengan memori akses acak tak terbatas dan 'program' terbatas yang menentukan kapan harus membaca, menulis, dan bergerak melintasi memori tersebut, kapan harus berhenti dengan hasil tertentu, dan apa yang harus dilakukan selanjutnya. Input ke mesin Turing dimasukkan ke dalam memorinya sebelum dimulai (Gustafson).

Mesin Turing dapat membuat keputusan berdasarkan apa yang dilihatnya dalam memori - 'Bahasa' yang hanya mendukung +, -, *, dan / pada bilangan bulat bukanlah Turing lengkap karena tidak dapat membuat pilihan berdasarkan inputnya, tetapi mesin Turing dapat melakukannya.
Mesin Turing dapat berjalan selamanya - Jika kita mengambil Java, Javascript, atau Python dan menghapus kemampuan untuk melakukan segala jenis loop, GOTO, atau panggilan fungsi, itu tidak akan menjadi Turing lengkap karena tidak dapat melakukan komputasi arbitrer yang tidak pernah selesai. Coq adalah pembuktian teorema yang tidak dapat mengekspresikan program yang tidak berakhir, jadi tidak lengkap Turing.
Mesin Turing dapat menggunakan memori tak terbatas - Bahasa yang persis seperti Java tetapi akan berakhir setelah menggunakan lebih dari 4 Gigabyte memori tidak akan lengkap Turing, karena mesin Turing dapat menggunakan memori tak terbatas. Inilah sebabnya kita tidak dapat benar-benar membangun mesin Turing, tetapi Java masih merupakan bahasa Turing lengkap karena bahasa Java tidak memiliki batasan yang mencegahnya menggunakan memori tak terbatas. Inilah salah satu alasan ekspresi reguler tidak lengkap Turing.
Mesin Turing memiliki memori akses acak - Bahasa yang hanya memungkinkan Anda bekerja dengan memori melalui operasi push dan pop ke tumpukan tidak akan lengkap Turing. Jika saya memiliki 'bahasa' yang membaca string satu kali dan hanya dapat menggunakan memori dengan mendorong dan mengeluarkan dari tumpukan, ia dapat memberi tahu saya apakah setiap ( dalam string memiliki miliknya sendiri ) nanti dengan mendorong ketika melihat ( dan mengeluarkan ketika melihat ). Akan tetapi, ia tidak dapat memberi tahu jika setiap ( memiliki ) sendiri di kemudian hari dan setiap [ memiliki ] sendiri di kemudian hari (perhatikan bahwa ([)] memenuhi kriteria ini tetapi ([]] tidak). Mesin Turing dapat menggunakan memori akses acaknya untuk melacak () dan [] secara terpisah, tetapi bahasa ini dengan hanya tumpukan tidak dapat melakukannya.
Mesin Turing dapat mensimulasikan mesin Turing lainnya - Mesin Turing, ketika diberi 'program' yang sesuai, dapat mengambil 'program' mesin Turing lain dan mensimulasikannya pada input yang sembarangan. Jika Anda memiliki bahasa yang dilarang mengimplementasikan interpreter Python, bahasa tersebut tidak akan menjadi Turing lengkap.

Contoh bahasa Turing Complete

Python

Mendukung fungsi rekursif, loop (while, for), kondisi (if/else), dan pengelolaan memori. Dapat digunakan untuk menulis simulasi mesin Turing artinya Turing complete.

Java

Mendukung OOP, alur kontrol, struktur data kompleks, dan manajemen memori melalui objek. Mampu menyelesaikan semua masalah yang dapat diselesaikan mesin Turing.

Meski low-level, C memiliki semua kemampuan logis dan memori yang diperlukan. Banyak sistem operasi ditulis dengan C, membuktikan kekuatan komputasinya.

2.1.3 Turing Equivalent

Konsep terkait adalah Turing Equivalent – dua komputer P dan Q disebut ekuivalen jika P dapat mensimulasikan Q dan Q dapat mensimulasikan P.[4] Tesis Church–Turing menduga bahwa fungsi apa pun yang nilainya dapat dihitung oleh suatu algoritma dapat dihitung oleh mesin Turing, dan oleh karena itu jika komputer dunia nyata apa pun dapat mensimulasikan mesin Turing, maka komputer tersebut setara dengan mesin Turing. Mesin Turing universal dapat digunakan untuk mensimulasikan mesin Turing apa pun dan dengan perluasan aspek komputasional murni dari setiap komputer dunia nyata yang mungkin.

Banyak bahasa komputasi yang tidak Turing-lengkap. Salah satu contohnya adalah himpunan bahasa reguler, yang dihasilkan oleh ekspresi reguler dan yang dikenali oleh finite automata. Ekstensi finite automata yang lebih canggih tetapi masih belum Turing-lengkap adalah kategori pushdown automata dan tata bahasa bebas konteks, yang umumnya digunakan untuk menghasilkan pohon parse dalam tahap awal kompilasi program. Contoh lebih lanjut mencakup beberapa versi awal bahasa pixel shader yang tertanam dalam ekstensi Direct3D dan OpenGL.

Dalam bahasa pemrograman fungsional total, seperti Charity dan Epigram, semua fungsi bersifat total dan harus diakhiri. Charity menggunakan sistem tipe dan konstruksi kontrol berdasarkan teori kategori, sedangkan Epigram menggunakan tipe dependen. Bahasa LOOP dirancang sedemikian rupa sehingga hanya menghitung fungsi yang bersifat rekursif primitif. Semua ini menghitung subset yang tepat dari total fungsi komputasi, karena himpunan lengkap dari total fungsi komputasi tidak dapat dihitung secara komputasi. Selain itu, karena semua fungsi dalam bahasa ini bersifat total, algoritme untuk himpunan yang dapat dihitung secara rekursif tidak dapat ditulis dalam bahasa ini, berbeda dengan mesin Turing.

Meskipun kalkulus lambda (tanpa tipe) bersifat Turing-lengkap, kalkulus lambda dengan tipe sederhana tidak demikian (“Turing completeness - Wikipedia”).

2.2. Manfaat Mengetahui Turing Complete dan Turing Equivalent

2.2.1 Pentingnya Turing Completeness

Mengetahui bahwa suatu bahasa atau sistem bersifat Turing complete sangat bermanfaat, terutama dalam konteks desain perangkat lunak, pemilihan bahasa pemrograman, dan analisis sistem komputasi. Berikut beberapa manfaat utamanya:

1. Menilai Kemampuan Ekspresif Bahasa. Bahasa yang Turing complete mampu mengekspresikan seluruh algoritma yang dapat dihitung secara teoritis. Hal ini penting saat mendesain sistem perangkat lunak kompleks dan menentukan apakah bahasa tertentu bisa menggantikan bahasa lain. Contoh: Python, Java, dan C semuanya Turing complete bisa menyelesaikan masalah yang sama walaupun cara implementasinya berbeda.

2. Mendukung Pengembangan Sistem Universal. Bahasa Turing complete memungkinkan kita membuat interpreter atau compiler untuk bahasa lain, serta sistem yang fleksibel seperti Mesin virtual (misalnya JVM), Emulator dan kompilator lintas platform

3. Memahami Batas Teoretis Komputasi. Turing completeness membantu kita menyadari bahwa: Ada masalah yang tidak bisa diselesaikan oleh semua bahasa

2.2.2 Pentingnya Turing Equivalence

1. Interoperabilitas Sistem. Karena dua bahasa Turing equivalent dapat menyelesaikan masalah yang sama, kita bisa memilih bahasa berdasarkan kebutuhan praktis (misal: performa, sintaks, dukungan komunitas), bukan hanya kapabilitas teoretis. Mengubah satu bahasa ke bahasa lain tanpa kehilangan fungsionalitas.

2. Reduksi Masalah Antar Model. Dalam ilmu komputer teoretis, kita sering memindahkan masalah dari satu model ke model lain. Misalnya dari lambda calculus ke Turing machine,

3. Pemahaman Lebih Mendalam tentang Komputasi. Konsep Turing equivalence mengajarkan bahwa “komputasi” itu tidak terikat dengan perangkat fisik atau bahasa tertentu, tapi lebih kepada kemampuan menyelesaikan masalah logis — tak peduli apakah ia ditulis dalam Python, lambda calculus, atau Brainfuck.

BAB IV

KESIMPULAN

Berdasarkan pembahasan mengenai Church-Turing Thesis, serta konsep-konsep lanjutan seperti Turing Complete dan Turing Equivalent, dapat disimpulkan bahwa:

Church-Turing Thesis menjadi fondasi utama dalam teori komputasi modern. Gagasan bahwa setiap fungsi yang dapat dihitung secara efektif dapat dihitung oleh mesin Turing, memberi batas teoretis tentang apa yang bisa diselesaikan oleh komputer mana pun.
Suatu sistem dikatakan Turing Complete jika memiliki kemampuan yang setara dengan mesin Turing, yakni dapat menyelesaikan setiap fungsi komputasi yang bisa dihitung secara algoritmik. Mengetahui apakah suatu bahasa Turing complete penting dalam menentukan fleksibilitas bahasa tersebut dalam membangun sistem yang kompleks dan universal.
Turing Equivalent adalah konsep yang menyatakan bahwa dua sistem memiliki kekuatan komputasi yang sama. Ini memungkinkan kita untuk menyederhanakan analisis, mengalihkan implementasi antar bahasa, dan membandingkan sistem komputasi berdasarkan kemampuannya, bukan sintaks atau performa.

DAFTAR PUSTAKA

Boker, Udi, and Nachum Dershowitz. “The Church-Turing Thesis over Arbitrary Domains.” SPRINGER NATURE Link, Pillars Of Computer Science, 2008, https://link.springer.com/chapter/10.1007/978-3-540-78127-1_12.

“Church–Turing thesis - Wikipedia.” Wikipedia, the free encyclopedia, https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis. Accessed 13 June 2025.

Goldin, Dina, and Peter Wegner. “The Church-Turing Thesis: Breaking the Myth.” SPRINGER NATURE Link, New Computational Pardigms, 2005, https://link.springer.com/chapter/10.1007/11494645_20. Accessed 13 06 2005.

Gustafson, Gordon. “What Is Turing Complete?” stackoverflow, Mark Harrison & dlinsin, 23 Desember 2017, https://stackoverflow.com/questions/7284/what-is-turing-complete?__cf_chl_tk=p5G89gbhAnh2Dg6MMJ99Nz5wQGkPT5spbqT._h8wlXc-1749801821-1.0.1.1-W.N.rQO9oYshIA1abqsq.Hz9gQayBJ7aqRaec8tsY_Q. Accessed 13 Juni 2025.

Hewitt, Edwin. “The Church-Turing Thesis (Stanford Encyclopedia of Philosophy).” Stanford Encyclopedia of Philosophy, 8 January 1997, https://plato.stanford.edu/entries/church-turing/#ThesHist. Accessed 13 June 2025.

“Turing completeness - Wikipedia.” Wikipedia, the free encyclopedia, https://en.wikipedia.org/wiki/Turing_completeness#Formal_definitions. Accessed 13 June 2025.

Cari Blog Ini

Kuliah PBO

Church-Turing Thesis dan Kaitannya dengan Bahasa Pemrograman

PENDAHULUAN

1.1 Latar Belakang