Menentukan apakah Bahasa Turing Lengkap sangat penting ketika merancang bahasa. Ini juga merupakan tugas yang cukup sulit bagi banyak bahasa pemrograman esoteris untuk memulai, tetapi mari kita mulai saja. Mari kita membuat beberapa bahasa pemrograman yang begitu sulit untuk dibuktikan Turing Lengkap sehingga bahkan ahli matematika terbaik di dunia akan gagal membuktikannya dengan cara apa pun. Tugas Anda adalah menyusun dan mengimplementasikan bahasa yang Kelengkapan Turing bergantung pada masalah utama yang belum terpecahkan dalam Matematika .
Aturan
Masalah yang Anda pilih harus diajukan setidaknya 10 tahun yang lalu dan harus dipecahkan, sejak posting pertanyaan ini. Ini bisa berupa dugaan yang bisa dibuktikan dalam matematika, bukan hanya salah satu dari yang terdaftar di halaman Wikipedia .
Anda harus memberikan spesifikasi bahasa dan implementasi dalam bahasa yang ada.
Bahasa pemrograman harus Turing lengkap jika dan hanya jika dugaan itu berlaku. (atau jika dan hanya jika dugaan tidak berlaku)
Anda harus menyertakan bukti mengapa Turing lengkap atau tidak lengkap berdasarkan dugaan yang dipilih. Anda dapat mengasumsikan akses ke memori tidak terbatas ketika menjalankan interpreter atau program yang dikompilasi.
Karena kita prihatin dengan Turing Completeness I / O tidak diperlukan, namun tujuannya adalah untuk membuat bahasa yang paling menarik sehingga dapat membantu.
Ini adalah kontes popularitas sehingga jawaban dengan suara terbanyak akan menang.
Kriteria Target
Apa yang harus dilakukan dengan jawaban yang baik? Berikut adalah beberapa hal yang harus dicari ketika memilih tetapi tidak secara teknis diperlukan
Seharusnya bukan tambalan sederhana dari bahasa yang ada. Mengubah bahasa yang ada agar sesuai dengan spesifikasinya baik-baik saja tetapi menambal dengan syarat tidak disarankan karena membosankan. Seperti yang dikatakan oleh ais523 dalam Nineteeth Byte:
Saya lebih suka membuat gimmick esolang saya lebih kuat dimasukkan ke dalam bahasa
Itu harus menarik sebagai bahasa esoterik mandiri.
sumber
Jawaban:
Legendre
Bahasa ini hanya menyelesaikan-Turing jika dan hanya jika dugaan Legendre salah, yaitu terdapat bilangan bulat n> 0 sehingga tidak ada bilangan prima antara n ^ 2 dan (n + 1) ^ 2. Bahasa ini mengambil beberapa inspirasi dari Underload, meskipun dalam beberapa hal sangat berbeda dari itu.
Program di Legendre terdiri dari serangkaian bilangan bulat positif (0 khususnya dilarang, karena pada dasarnya meniadakan seluruh tujuan bahasa). Setiap integer sesuai dengan perintah dasar di Legendre, atau yang potensial yang ditentukan pengguna. Perintah yang ditugaskan padanya didasarkan pada jumlah bilangan prima antara kuadratnya dan bilangan bulat berikutnya (setara dengan urutan OEIS A014085 ).
Perintah bahasa memodifikasi tumpukan, yang dapat menampung bilangan bulat positif besar yang sewenang-wenang. Jika tumpukan pernah menampung 0, 0 segera dihapus. Secara rinci, perintahnya adalah:
2 (integer terkecil yang menghasilkan perintah ini: 1): Dorong integer berikutnya dalam program ke stack.
3 (integer penghasil terkecil: 4): Letakkan integer atas pada stack dan jalankan perintah yang terkait dengannya.
4 (terkecil: 6): Pop the top integer. Jika itu 1, tambahkan bilangan bulat atas di tumpukan.
5 (10): Tukar dua item tumpukan teratas.
6 (15): Kurangi integer atas pada tumpukan. Jika hasilnya 0, pop 0 dan buang.
7 (16): Gandakan bilangan bulat atas pada tumpukan.
8 (25): Menghentikan eksekusi dan mencetak konten tumpukan.
Ini adalah set instruksi dasar, yang tidak dapat melakukan sesuatu yang menarik, apalagi perulangan. Namun, ada perintah lain, yang dapat diakses hanya jika dugaan Legendre terbukti salah.
Jika perintah ini entah bagaimana dapat diakses, bahasa menjadi Turing-lengkap, karena seseorang dapat mensimulasikan mesin Minsky di dalamnya.
Ketika perintah 8 dijalankan atau akhir dari program tercapai, program berakhir dan karakter (Unicode) yang sesuai dengan setiap bilangan bulat pada tumpukan dicetak.
Contoh program
Program sederhana ini mendorong angka 2, kemudian 3 dan akhirnya 10, sebelum mengeksekusi 4 (perintah: 3), yang menyebabkan 10 (perintah: 5) muncul dan dieksekusi, menukar 2 dan 3.
Program ini menunjukkan penggunaan korespondensi integer-ke-perintah tidak langsung. Pertama, 5 ditekan, lalu 15 dan 1, menggunakan tiga cara pengkodean 2 perintah yang berbeda. Kemudian, angka 1 muncul dan hasilnya, angka 15 bertambah menjadi angka 16, dan akhirnya dieksekusi. Program berakhir dengan dua contoh nomor 5 pada tumpukan.
Program ini menunjukkan penggunaan perintah 0, menggunakan? sebagai nomor pengganti. Program pertama-tama menyimpan '1 5' di fungsi 9, lalu '15 31 'di 10, sebelum menjalankan fungsi 9 (menggunakan 24), yang mendorong 5 ke tumpukan, dan berulang kali menurunkannya, hingga mencapai 0 dan dihapus . Kemudian, program terhenti.
Mesin Minsky
Untuk mengonversi mesin Minsky ke kode Legendre, perintah 0 harus digunakan. Karena perintah ini tidak dapat diakses kecuali dugaan Legendre salah, saya telah menggunakan pengganti? sebagai gantinya.
Perhatikan bahwa semua nama jalur instruksi mesin Minsky harus memiliki bilangan bulat dengan korespondensi A014085 yang berbeda satu sama lain dan perintah dasar serta 24 (9) dan 31 (10).
Inisialisasi: x INC (A / B) y:SEBUAH:
B:
x DEC (A / B) yz:SEBUAH:
B:
x HALT:Untuk membuat program akhir, tambahkan semua bagian (dengan x, y, z digantikan oleh rekan-rekan mereka) dan tambahkan bilangan bulat tunggal untuk memulai instruksi pertama dalam rantai. Ini harus membuktikan kelengkapan Turing bahasa dalam kasus dugaan Legendre terbukti salah dengan contoh balik.
Penerjemah
Penerjemah ini ditulis dengan Python (3), dan telah diuji pada ketiga contoh di atas. Gunakan flag -a / - allowZero untuk mengizinkan? untuk digunakan, -f / - file untuk menjalankan kode langsung dari file dan -s / - stackOut untuk menampilkan stack sebagai daftar Python. Jika tidak ada file yang diberikan, interpreter memasuki semacam mode REPL, yang paling baik digunakan dengan --stackOut.
sumber
Serikat Tertutup
Bahasa pemrograman ini Turing lengkap jika dugaan Set Serikat-tertutup tidak benar.
Kontrol
Daftar Perintah:
x ++ Increment x (INC)
x-- Decrement x (DEC)
j (x, y) Tambahkan set instruksi x jika y adalah 0 hingga akhir antrian instruksi
Semua variabel diinisialisasi sebagai 0
Sintaksis
Program ditulis sebagai seperangkat perintah.
Command1 Command2 Command3 ...
Command1 Command2 ...
...
Untuk menentukan apakah program ditutup dengan gabungan, setiap set hanya bertanggung jawab atas daftar perintah berbeda yang ada di set
j (x, y)! = J (a, b)
+ (x)! = + (Y)
Jika ada jenis perintah (+, -, j) muncul di setidaknya setengah set, itu tidak melakukan apa-apa.
Program dapat berakhir jika tidak ada instruksi di ujung antrian instruksi
Loop tak terbatas, termasuk loop kosong, dapat dicapai menggunakan j (x, y)
Penerjemah
Tampilkan cuplikan kode
Turing Kelengkapan
Jika ketiga perintah, j (x, y), increment, decrement semua perintah tersedia, sehingga mesin Minsky dapat disimulasikan.
Setiap set dengan hanya j (x, y) yang dicapai menggunakan j (x, y) adalah HALT
x ++ adalah INC
x-- adalah DEC
j (x, y) adalah JZ
Jika serikat tertutup menetapkan dugaan itu benar, setidaknya satu dari tiga perintah akan selalu dinonaktifkan, sehingga membuat bahasa ini tidak mungkin untuk menyelesaikan Turing.
sumber
Bilangan prima kulit
Bahasa ini berfungsi pada dua kaset yang berpotensi tak terbatas, di mana setiap lokasi rekaman itu dapat menyimpan bilangan bulat sewenang-wenang. Kedua kaset diisi dengan
-1
di awal. Ada juga dua kepala kaset yang mulai pada posisi 0 pada kedua kaset.Juru bahasa pertama akan membaca input, dan menyimpan nilai-nilai ke dalam rekaman (data) pertama, mulai dari posisi 0.
Kemudian akan membaca program yang disediakan. Untuk setiap nomor yang dihadapinya, pertama-tama akan memeriksa apakah nilainya merupakan prime Fermat atau tidak. Jika ya, itu akan menulis ke rekaman (instruksi) kedua yang merupakan Fermat prima, jika tidak maka akan menulis
-1
ke rekaman instruksi.Selanjutnya periksa nilai pada penunjuk instruksi, dan lakukan salah satu hal berikut ini:
-1
atau kurang: Keluar dari program0
: Pindahkan posisi rekaman data satu ke kiri. Pindahkan pita instruksi satu ke kanan1
: Pindahkan posisi rekaman data satu ke kanan. Pindahkan pita instruksi satu ke kanan2
: Meningkatkan nilai pada posisi rekaman data. Pindahkan pita instruksi satu ke kanan3
: Kurangi nilai pada posisi rekaman data. Pindahkan pita instruksi satu ke kanan4
: Jika nilai pada posisi rekaman data saat ini adalah nol, kemudian pindahkan pita instruksi ke kanan, hingga Anda mencapai nilai yang cocok5
(atau lebih besar) pada pita instruksi, atau sesuatu yang lebih kecil dari0
. Jika itu adalah5
(atau lebih besar), pindahkan penunjuk instruksi ke kanan sekali lagi, jika itu lebih kecil daripada0
kemudian keluar dari program. Jika nilai posisi rekaman data saat ini tidak nol, cukup pindahkan pita instruksi satu ke kanan5
atau lebih: Pindahkan penunjuk instruksi ke kiri, sampai Anda mencapai nilai yang sesuai4
, atau Anda menemukan sesuatu yang kurang0
. Dalam kasus yang terakhir, keluar dari program.(dengan mencocokkan
5
(atau lebih) dan4
nilai - nilai itu berarti bahwa ketika mencari nilai yang tepat pada pita instruksi setiap kali ia menemukan nilai yang sama dengan perintah awal (baik5
(atau lebih) atau4
), ia harus melewati angka yang sesuai dari nilai lain (4
atau5
(atau lebih) masing-masing) pada pencarian)Loop, sampai instruksi mengatakan Anda harus keluar dari program.
Ketika program keluar, output nilai pada rekaman data dari posisi
0
hingga posisi rekaman pertama yang berisi-1
nilai.Bukti
Perhatikan bahwa bahasa tersebut pada dasarnya memetakan ke penerjemah Brainfuck IO-kurang, di mana
F_5
diperlukan untuk dapat melakukan segala jenis loop yang tepat.Namun berdasarkan dugaan prime Fermat hanya ada 5 prima Fermat (
F_0
-F_4
). JikaF_5
ada bahasanya adalah Turing-complete, seperti yang kita tahu bahwa Brainfuck adalah Turing-complete. Namun, tanpaF_5
Anda tidak akan dapat melakukan percabangan atau pengulangan, pada dasarnya mengunci Anda menjadi program yang sangat sederhana.Penerapan
(diuji dengan ruby 2.3.1)
Contoh:
Ini akan menulis
H
(kependekan dariHello World!
) ke layar dengan baris baru:Simpan sebagai
example.fermat
dan jalankan seperti ini (catatan: Anda selalu harus memiliki input):Contoh berikut ini akan melakukan cypher gaya Caesar sederhana dengan menambah setiap nilai input dengan satu. Anda jelas harus mengganti
?
dengan prime 5 Fermat:Anda dapat mencobanya yang berfungsi dengan mengaktifkan mode cheat dan menggunakan
2 4 1 2 5 3
sebagai kode sumber:sumber
5
. Saya harap mereka memiliki keyboard yang bagus.Menelan dg Kelapa v2
Karena versi sebelumnya memiliki kesalahan yang membuatnya tidak valid untuk kontes ini, dan saya tidak ingin mendapatkan upvotes dari jumlah versi sebelumnya untuk versi ini yang sangat berbeda, versi ini sedang dikirim sebagai posting baru.
Bahasa ini bukan Turing yang lengkap jika Dugaan Collatz dapat dibuktikan untuk semua bilangan bulat positif. Kalau tidak, bahasa Turing lengkap.
Bahasa ini didasarkan dari Kardinal .
Pertama, contVal program dihitung menggunakan rumus
contVal = jumlah (jumlah (nilai ASCII dari baris) * 2 ^ (nomor baris-1))
Selanjutnya, 2 Swallows menuju arah yang berlawanan dibuat pada setiap A atau E dan semua pernyataan belokan bersyarat diatur untuk menunggu inisialisasi.
Menelan yang dibuat di E mengarah ke kiri / kanan dan menelan yang dibuat di A mengarah ke atas / bawah.
Akhirnya, kode akan melakukan langkah-langkah sampai semua pointer telah dihapus atau contVal telah jatuh ke satu.
Pada setiap langkah, jika contVal% 2 == 0 itu akan dibagi 2, jika tidak, itu akan dikalikan tiga dan bertambah satu.
Perintah:
0: atur nilai ke 0
+: nilai kenaikan sebesar 1
>: ubah arah ke kanan
v: ubah arah ke bawah
<: ubah arah ke kiri
^: ubah arah ke atas
R: Pointer berikutnya setelah pointer pertama bandingkan dengan nilai dari pointer pertama. Jika sama, lurus, kalau tidak belok kanan.
L: Pointer berikutnya setelah pointer pertama membandingkan dengan nilai pointer pertama. Jika sama, lurus, kalau tidak belok kiri.
E: Gandakan pointer tetapi menuju ke arah kiri dan kanan
A: Gandakan pointer tetapi menuju ke arah atas dan ke bawah
? : Hapus pointer jika nilainya 0
Tampilkan cuplikan kode
Penjelasan:
Jika Dugaan Collatz dapat dibuktikan untuk semua bilangan bulat positif, durasi dari setiap program yang dijalankan dalam bahasa ini terbatas, karena contVal akan selalu konvergen ke 1, sehingga mengakhiri program.
Kalau tidak, saya hanya perlu membuktikan bahwa bahasa ini dapat menerapkan fungsi - fungsi berikut
Peningkatan: yang diwakili oleh +
Constant 0: yang diwakili oleh 0
Akses variabel: variabel disimpan sebagai pointer saat mereka melakukan perjalanan
Rangkaian pernyataan: dengan mengubah jarak yang ditempuh ke operasi, urutan pengoperasian yang dilakukan dapat diubah
Untuk loop: Dalam bahasa ini
akan bertindak sebagai for for> count hingga 1 (kode lebih lanjut dapat ditambahkan ke loop)
Begitu pula kodenya
Akan bertindak sebagai do sampai sama dengan nilai kondisional yang ditetapkan dalam loop R.
sumber
contVal
pada setiap langkah (dan karena itu jika dugaan itu benar, tidak ada loop tak terbatas) - tetapi saya tidak melihat bahwa secara eksplisit dinyatakan di mana saja dalam jawaban. ??Kesempurnaan / Ketidaksempurnaan
Wah, itu menyenangkan.
Kesempurnaan / Ketidaksempurnaan hanya lengkap jika ada angka sempurna yang tak terbatas. Jika ada, itu disebut Kesempurnaan, dan jika tidak ada, itu disebut Ketidaksempurnaan. Sampai misteri ini terpecahkan, ia memegang kedua nama.
Angka sempurna adalah angka yang jumlah pembagi-nya sama dengan angka, jadi enam adalah angka sempurna karena
1+2+3=6
.Kesempurnaan / Ketidaksempurnaan memiliki fungsi-fungsi berikut:
Kesempurnaan / Ketidaksempurnaan berbasis tumpukan, dengan tumpukan yang diindeks nol.
Perintah:
p(x, y)
: mendorong x ke tumpukan di posisi y.z(x, y)
: mendorong x ke tumpukan di posisi y, menghilangkan apa yang sebelumnya di posisi ke-yr(x)
: menghapus item xth dari stackk(x)
: mengembalikan item ke-X di tumpukana(x, y)
: menambahkan x dan y. Ketika digunakan dengan string, itu menempatkan mereka bersama-sama dalam urutan xy.s(x, y)
: kurangi y dari x. dengan string, menghapus len (y) terakhir dari xm(x, y)
: mengalikan x dan y. Jika digunakan dengan string, gandakan x kali len y.d(x, y)
: membagi x dengan yo(x)
: cetakan xi(x, y)
: jika x bernilai true, maka ia menjalankan fungsi yn()
: mengembalikan penghitung blok kode sedang dipanggil.q()
: mengembalikan panjang tumpukant()
: input penggunae(x, y)
: Jika x adalah bilangan bulat, jika x dan y memiliki nilai yang sama, maka ini mengembalikan 1. jika y adalah string maka ia mendapatkan panjang y. jika x adalah sebuah string, maka itu mengkonversi y menjadi sebuah string dan memeriksa apakah mereka sama, dan jika mereka, mengembalikan 1. Jika tidak maka mengembalikan 0.l(x, y)
: jika x lebih besar dari y, maka mengembalikan 1. Jika ada string, maka ia menggunakan panjang string.b()
: menghentikan program.c(x, y)
: menjalankan x, lalu y.Untuk mendapatkan yang setara dengan Python
and
, kalikan dua nilai bersama. Untukor
, tambahkan nilainya, dan untuknot
, kurangi nilainya dari 1. Ini hanya berfungsi jika nilainya 1 atau 0, yang dapat dicapai dengan membagi angka dengan sendirinya.Tipe data: bilangan bulat dan string. String dilambangkan dengan
''
, dan semua angka non-integer dibulatkan.Sintaksis:
Kode terdiri dari fungsi bersarang dalam sepuluh
{}
detik. Sebagai contoh, sebuah program yang akan mendapatkan masukan dan mencetaknya menambahkan akan:{o(a(t(), t()))}
. Di latar belakang program ada penghitung yang dimulai pada 0 dan berlanjut dengan 1 setiap kali mengeksekusi blok kode. Blok kode pertama berjalan pada0
, dan seterusnya. Setelah sepuluh blok kode dieksekusi, yang keenam dieksekusi setiap kali penghitung mencapai angka sempurna. Anda tidak perlu memiliki semua sepuluh blok kode untuk program untuk bekerja, tetapi Anda perlu 7 jika Anda ingin membuat loop. Untuk lebih memahami bagaimana bahasa ini bekerja, menjalankan program berikut, yang mencetak meja setiap kali counter mencapai angka sempurna:{}{}{}{}{}{}{o(n())}
.Penerjemah dapat ditemukan di sini: repl.it/GL7S/37 . Pilih 1 dan ketik kode Anda di terminal, atau rekatkan kode Anda di
code.perfect
tab dan pilih 2 saat Anda menjalankan. Ini akan masuk akal ketika Anda mencobanya.Bukti kelengkapan Turing / kurangnya kelengkapan Turing.
Menurut artikel pertukaran tumpukan rekayasa perangkat lunak ini , Turing yang lengkap harus dapat memiliki bentuk pengulangan lompatan bersyarat, dan memiliki cara untuk membaca atau menulis memori. Ia dapat membaca / menulis memori dalam bentuk stack, dan itu dapat berulang karena fakta bahwa blok kode ke-6 dieksekusi setiap kali penghitung mencapai angka sempurna. Jika ada angka sempurna dalam jumlah tak terbatas, ia dapat berulang tanpa batas dan Turing lengkap, dan sebaliknya tidak.
Penerjemah Self Bitwise Cyclic Tag yang mengambil 5 karakter, 1 atau 0, sebagai input:
Dapat diperluas untuk mengambil sejumlah karakter sebagai input. Itu bisa mengambil input yang tak terbatas, tetapi hanya jika ada angka sempurna yang tak terbatas!
sumber
Sol
Bahasa pemrograman ini Turing lengkap jika dugaan Scholz benar.
Saya menulis bahasa ini karena @SztupY mengatakan bahwa tidak akan ada hasil yang bergantung pada dugaan untuk menjadi Turing yang lengkap
Daftar Perintah
Dengan perintah ini, bahasa ini dapat mensimulasikan mesin Minsky
Penerjemah
Saya akan sangat menyarankan tidak menjalankan ini. Ini menggunakan metode yang sangat lambat untuk memeriksa rantai penjumlahan.
Tampilkan cuplikan kode
Turing kelengkapan
Bahasa ini menggunakan penghitung untuk sejumlah perintah yang dijalankan yang mengecek dugaan Scholz untuk memodifikasi kelengkapan turing bahasa.
Jika dugaan Scholz benar, program ini bekerja persis seperti mesin Minsky normal dengan
Increment
Decrement
Jump jika Zero
Stop
Namun, jika dugaan Scholz salah, penghitung akhirnya akan mencapai nilai yang dugaan Scholz tidak berlaku. Karena bahasa telah dirancang untuk keluar setelah mencapai angka yang dugaan Scholz salah, program akan keluar setiap kali setelah menjalankan banyak perintah. Oleh karena itu, semua program akan memiliki panjang yang terbatas. Karena ini tidak setuju dengan persyaratan agar bahasa Turing lengkap,
bahasa tidak akan menjadi Turing lengkap jika dugaan Scholz salah
sumber
Bertunangan
Bertunangan Github .
Readme dan spesifikasinya ada di github, di bawah "README.txt".
Secara umum, program bertunangan terdiri dari pasangan garis, yang panjangnya adalah pasangan prima kembar atau pasangan bertunangan (tidak ada duplikat dapat terjadi). Program ini dijalankan dengan menemukan "himpunan bagian yang lentur" dari baris pertama pada pasangan di dalam baris kedua. Jumlah himpunan bagian tersebut, dikombinasikan dengan jarak levenshtein antara baris kedua asli dan baris kedua tanpa himpunan bagian yang lentur, menentukan perintah untuk mengeksekusi.
Saya akan mengutip bukti untuk posting ini:
sumber
b
. Ini mengartikan program BF, yang ditempatkan setelahnya, sepertib+++++.
. Namun ukuran program dibatasi hingga 10 karakter. Meskipun dapat menafsirkan BF, ia tidak dapat menghitung semua program yang dapat dilakukan mesin Turing.Paritas yang damai
Bahasa ini didasarkan pada apakah ada angka persahabatan dengan paritas yang berlawanan .
Perintah
Mengontrol aliran
Program berputar berulang kali dari kiri ke kanan sebelum kembali ke awal. Jika menemukan "j", ia memeriksa nilai untuk menentukan apakah harus mengubah baris. Jika nomor tersebut adalah angka damai dengan paritas yang berlawanan dengan pasangannya, maka turun satu baris (berputar kembali ke atas), Jika tidak, jika nomor tersebut adalah angka damai, maka naik satu baris jika belum berada di baris atas.
Program hanya dapat berakhir jika program mencapai x pada baris apa pun di luar baris atas.
Turing Kelengkapan
Program ini dapat digunakan untuk mensimulasikan mesin Minsky dengan asumsi bahwa ada sepasang nomor yang bersahabat dengan paritas yang berlawanan.
j, {dan} dapat digunakan untuk mensimulasikan JZ (r, x) meskipun ia akan memeriksa angka damai sebagai lawan dari nol.
+ adalah INC (r)
- adalah DEC (r)
x adalah HALT
Jika Anda tidak dapat meninggalkan baris pertama, perintah x dan} tidak melakukan apa pun. Hal ini menyebabkan program tidak dapat memasuki kondisi HALT kecuali jika itu adalah program kosong. Oleh karena itu, di bawah uraian bahwa kelengkapan Turing memerlukan status HALT , bahasanya akan menjadi tidak lengkap.
Penerjemah
Tampilkan cuplikan kode
sumber
Garis baru
Penafian: Agak berantakan dan cukup sederhana. Ini adalah bahasa pertama yang pernah saya tulis dan dugaan adalah satu-satunya yang saya mengerti. Saya tahu pengguna lain memiliki jawaban yang lebih panjang dengan jawaban yang sama tetapi saya memutuskan untuk tetap menulis ini.
Untuk menulis di Newline, Anda harus memiliki banyak waktu dan baris baru (
\n
). Ini berhasil karena dugaan Legendre benar. Setiap operator harus jatuh pada angka dalam dugaan Legendre yang kita mulai dengan n = 1. Setiap kali Anda memiliki operator, Anda mengambil jumlah \ n dan memasukkannya ke dalam dugaan Legendre dan mendapatkan kisaran yang jumlah prima berikutnya dari \ n harus masuk. Jadi untuk memulai Anda lakukan\n\n
maka Anda pindah ke operator lalu ke operator\n
lain kita berada di 3 baris baru. Sekarang yang berikutnya adalah 5 sehingga Anda menambahkan\n\n
dan pada operator memastikan bahwa garis operator terakhir memiliki jumlah baris baru yang tepat sehingga Anda berada pada jumlah prima yang termasuk dalam dugaan Legendre yang kami mulai.Bilangan (array) seperti variabel. Setiap kali seorang operator berjalan (yang menggunakan angka) akan bertambah.
Selama kami memiliki bilangan prima tak terbatas yang mengikuti aturan, bahasa ini memiliki rekaman yang tidak terbatas.
Mesin Minsky
Bagaimana itu bekerja:
Cobalah di KhanAcademy .
sumber
Taggis
Taggis adalah bahasa berdasarkan sistem tag .
Kelengkapan turing Taggis didasarkan pada dugaan Collatz
Sintaksis
Sintaksis program Taggis hanyalah tiga string (aturan produksi) yang seluruhnya terdiri dari huruf a, b, dan c, dipisahkan oleh spasi.
Eksekusi
Satu-satunya status program Taggis adalah string yang terdiri dari tiga karakter yang sama.
Taggis mengimplementasikan sistem tag TS (3, 2), di mana dalam setiap langkah 2 huruf pertama dari "tag" saat ini dihapus, dan huruf pertama yang ada di bagian yang dihapus tersebut akan mendapatkan aturan produksi yang sesuai ditambahkan pada akhir string.
Sebagai contoh, program Taggis
bc a aaa
mengimplementasikan masalah 3n + 1, di mana iterasi diwakili oleh jumlaha
s yang sesuai dan langkah 3n + 1 diganti dengan (3n + 1) / 2 [1], yang mengarah ke output program:Turing kelengkapan
Tentu saja, sistem sederhana ini mungkin tampak terlalu sederhana untuk meniru kelengkapan Turing, tetapi ternyata setiap mesin Turing dengan 2 simbol (kelas yang mencakup mesin universal) dapat dikonversi ke sistem tag dengan 2 karakter yang dihapus dari kepala, dan aturan produksi 32 * m, di mana
m
jumlah negara bagian dalam mesin Turing.Mesin Turing universal terkecil yang diketahui dengan hanya 2 simbol menggunakan 18 negara dan dengan demikian sistem tag yang sesuai berisi aturan produksi 576 kekalahan [2].
Namun, kelas komputasi dari himpunan semua sistem tag dengan 3 produksi dan 2 simbol yang dihapus terkait dengan Collatz Conjecture [2]. Jika dugaan Collatz terbukti salah, maka Taggis adalah Turing-complete. Jika tidak, ini didasarkan pada masalah LAIN yang belum terpecahkan dalam matematika, menemukan mesin Turing yang lebih kecil daripada
yang setara dengan fungsi Collatz asli sebagai 3n + 1 dari yang aneh
n
akan selalu genap dan oleh karena itu pembagian dapat diterapkan secara otomatisSistem tag dan fungsi seperti Collatz, Liesbeth De Mol ,
sumber