Ringkasan:

Untuk bahasa apa pun, berapakah jumlah karakter unik terkecil untuk bahasa Anda yang akan Turing-Lengkap ?

Tantangan:

Untuk bahasa apa pun yang Anda pilih, temukan subset karakter terkecil yang memungkinkan bahasa Anda Selesai-Turing. Anda dapat menggunakan kembali rangkaian karakter Anda sebanyak yang Anda inginkan.

Contoh:

• JavaScript: +!()[]( http://www.jsfuck.com )

• Brainfuck: +<>[](mengasumsikan ukuran sel pembungkus)

• Python 2: ()+1cehrx(terbuat dari skrip seperti exec(chr(1+1+1)+chr(1)))

Mencetak:

Tantangan ini dinilai dalam karakter , bukan byte . Misalnya, Skor untuk contoh adalah 6, 5, dan 9.

Catatan:

• Tantangan ini berbeda dari yang lain dalam arti bahwa Anda hanya menggunakan bahasa Anda untuk Menyelesaikan Turing (belum tentu dapat menggunakan setiap fitur bahasa).

• Meskipun Anda bisa, tolong jangan memposting jawaban tanpa mengurangi karakter yang digunakan. Contoh: Brainfuck dengan 8 karakter (karena setiap karakter lainnya adalah komentar secara default.)

• Anda HARUS memberikan setidaknya penjelasan singkat tentang mengapa subset Anda Turing-Lengkap.

Haskell, 4 karakter

()=;

Dengan ()=kita dapat mendefinisikan S, K dan I. Definisi harus dipisahkan oleh salah satu ;atau NL.

Kami mendefinisikan (==)sebagai S (baris kedua menunjukkan versi yang lebih mudah dibaca):

((=====)==(======))(=======)=(=====)(=======)((======)(=======))
( a     == b      ) c       = a      c       ( b       c       )

(===) sebagai K:

(=====)===(======)=(=====)
 a     === b      = a

dan (====)seperti saya:

(====)(=====)=(=====)
(====) a     = a 

Untungnya (==), (===), (====), dll adalah nama-nama fungsi / parameter yang valid.

Seperti yang ditunjukkan @ ais523, SKI tidak cukup dalam bahasa yang sangat diketik seperti Haskell, jadi kita perlu menambahkan kombinator fixpoint (=====):

(=====)(======)=(======)((=====)(======))
(=====) f      = f      ((=====) f      )

JavaScript (ES6), 5 karakter

Terima kasih kepada @ETHproductions dan @ATaco karena telah membantu dalam hal ini; ini adalah proyek kelompok, dan meskipun ide awalnya milik saya, banyak detailnya adalah milik mereka. Lihat diskusi obrolan tempat subset JavaScript ini dikembangkan di sini .

[]+=`

Sudah cukup mapan bahwa program Javascript apa pun dapat ditulis dengan karakter ( []()+!), tetapi 5 karakter tidak cukup . Namun, ini bukan tantangan tentang menulis JavaScript sewenang-wenang. Ini adalah tantangan tentang menulis bahasa Turing-lengkap, dan menggunakan fakta bahwa bahasa Turing-lengkap tidak memerlukan akses ke DOM, atau bahkan I / O interaktif, ternyata kita dapat menulis sebuah program dengan semua fungsi yang diperlukan , bahkan tanpa kemampuan untuk menjalankan evalatau yang setara.

Bootstrap dasar

JavaScript sangat fleksibel dengan tipe. Jadi misalnya, []adalah array kosong, tetapi +[]0, dan []+[]merupakan string nol. Khususnya, fakta bahwa kita dapat menghasilkan 0 dengan set karakter ini memungkinkan untuk mensimulasikan efek tanda kurung untuk pengelompokan; (a)dapat ditulis sebagai [a][+[]]. Kita dapat menggunakan trik semacam ini untuk menghasilkan berbagai karakter hanya dengan menggunakan +[]:

• [][+[]]is undefined(menjadi elemen pertama dari array kosong); begitu
• []+[][+[]]adalah "undefined"(pengerasan undefined); begitu
• [[]+[][+[]]]is ["undefined"](membungkus itu dalam sebuah array); begitu
• [[]+[][+[]]][+[]]adalah "undefined"(elemen pertama); begitu
• [[]+[][+[]]][+[]][+[]]adalah "u"(huruf pertama).

uadalah salah satu karakter yang paling mudah untuk dibuat, tetapi teknik serupa memungkinkan kami membuat berbagai karakter lain. The link yang sama seperti sebelumnya memberi kita daftar berikut karakter diakses dengan +[](ini adalah daftar yang sama seperti untuk +[](), tidak termasuk ,karena itu satu-satunya konstruksi yang menggunakan tanda kurung untuk tujuan lain selain pengelompokan / diutamakan):

0123456789acdefinotuvyIN (){}.

Kita tidak dapat mengeja kata-kata yang sangat berguna dari rangkaian karakter ini (ingat bahwa ini adalah rangkaian karakter yang dapat kita hasilkan sebagai string ; kita tidak dapat mengeksekusinya tanpa semacam eval). Karena itu, kita membutuhkan karakter lain. Kami akan menggunakannya =, karena nanti akan berguna, tetapi untuk saat ini, kami akan menggunakannya untuk mengeja operator perbandingan ==. Itu memungkinkan kita untuk menghasilkan falsedan true, yang dapat dirangkai dan diindeks menjadi, dan segera mari kita tambahkan lrske karakter yang dapat kita sertakan ke dalam string.

Sejauh ini, kata paling penting yang memungkinkan kita mengeja, yang tidak bisa kita lakukan sebelumnya adalah constructor. Sekarang, JavaScript memiliki sintaks akses properti yang terlihat seperti ini:

object.property

tetapi Anda juga dapat menulisnya seperti ini:

object["property"]

dan tidak ada yang mencegah kita menggunakan properti yang dihitung, alih-alih string literal. Dengan demikian kita dapat melakukan sesuatu di sepanjang garis

object["c"+"o"+"n"+"s"+"t"+"r"+"u"+"c"+"t"+"o"+"r"]

(dengan huruf yang dihasilkan seperti yang dijelaskan di atas; kode dengan cepat menjadi sangat panjang!); itu setara dengan object.constructor, yang memungkinkan kita mengakses konstruktor objek yang berubah-ubah.

Ada beberapa trik yang bisa kita lakukan dengan ini. Dari duniawi ke fantastis:

• Konstruktor suatu objek adalah fungsi. Khususnya, ia memiliki nama, dan nama itu adalah bagian dari pengetatan fungsi. Jadi misalnya, kita bisa lakukan [[]+[]][+[]]["constructor"]untuk mendapatkan konstruktor untuk sebuah string, yang namanya adalah String, dan kemudian menggantinya untuk mendapatkan Skarakter kapital . Ini sedikit memperluas alfabet kami, dan kami akan membutuhkan beberapa karakter baru nanti.

• Semua array memiliki konstruktor yang sama; []["constructor"] == []["constructor"]adalah true(tidak seperti [] == [], yang salah). Ini mungkin tampak kecil, tetapi ini sangat penting, karena memberi kita metode untuk menyimpan nilai secara terus-menerus; kita dapat mengatur properti acak pada konstruktor, dan membacanya kembali nanti. (Ini adalah salah satu alasan kami menggunakan =secara khusus, daripada salah satu cara lain untuk menghasilkan truedan false.) Misalnya, kami dapat mengevaluasi [[]["constructor"]["a"]=[]], dan kemudian membaca []["constructor"]["a"]dan mendapatkan kembali array yang sama dengan yang kami simpan di sana.

  Ini memenuhi salah satu persyaratan yang kita butuhkan untuk kelengkapan Turing , kemampuan untuk menyimpan dan mengambil jumlah data yang sewenang-wenang. Kita dapat membuat sel kontra menggunakan array dua elemen, mengambil nilai dari penyimpanan properti-konstruktor kami, dan kemudian menyimpannya kembali di tempat salah satu dari nilai-nilai itu, membiarkan kami membangun struktur data besar secara sewenang-wenang dalam memori; dan kita dapat mengaksesnya penyimpanan ini dengan melakukan kebalikannya, merobohkannya sepotong demi sepotong hingga data yang kita inginkan dapat diakses. Membaca bersifat merusak, tetapi itu dapat diterima karena kita memiliki lebih dari satu tempat untuk menyimpan data, sehingga kita dapat menyalinnya saat kita membacanya dan kemudian meletakkan salinannya kembali di lokasi semula.

• Hal ini memungkinkan kita untuk mendapatkan konstruktor untuk suatu fungsi (ada banyak fungsi yang dapat kita akses dengan alfabet terbatas kita; []["find"]yaitu Array.find, adalah yang paling mudah diakses, tetapi ada yang lain). Mengapa itu bermanfaat? Yah, kita sebenarnya bisa menggunakannya untuk tujuan yang diinginkan dari sebuah konstruktor, dan membangun fungsi! Sayangnya, dengan rangkaian karakter kami, kami tidak dapat meneruskan Function constructor ke string yang dihitung. Namun, penggunaan `tidak membiarkan kita memberikannya string literal (misalnya []["find"]["constructor"]`function body goes here`); ini berarti bahwa kita dapat mendefinisikan nilai-nilai khusus tipe fungsi dengan perilaku apa pun ketika dijalankan, selama kita dapat mengekspresikan perilaku itu sepenuhnya menggunakan []+=. Misalnya, []["find"]["constructor"]`[]+[]`adalah fungsi yang cukup membosankan yang menghitung string nol, membuangnya, dan keluar; bahwafungsi tidak berguna, tetapi yang lebih kompleks akan menjadi. Perhatikan bahwa meskipun fungsi tidak dapat mengambil parameter atau mengembalikan nilai, itu tidak masalah dalam praktik karena kita dapat menggunakan penyimpanan konstruktor-properti untuk berkomunikasi dari satu fungsi ke fungsi lainnya. Batasan lain adalah bahwa kita tidak dapat menggunakan `dalam fungsi.

  Sekarang, kita dapat mendefinisikan fungsi-fungsi khusus, tetapi yang menahan kita pada titik ini adalah kesulitan yang kita miliki dalam memanggilnya . Di tingkat atas program, kita dapat memanggil fungsi dengan ``, tetapi bisa memanggil fungsi hanya dari tingkat atas tidak memungkinkan kita melakukan semacam loop. Sebaliknya, kita membutuhkan fungsi untuk dapat saling memanggil.

  Kami menyelesaikan ini dengan trik yang cukup bagus. Ingat modal yang Skita hasilkan sebelumnya? Itu memungkinkan kita mengeja "toString". Kami tidak akan menyebutnya; kita dapat mengonversi berbagai hal menjadi string dengan menambahkannya []. Sebaliknya, kita akan menggantinya . Kita dapat menggunakan penyimpanan konstruktor untuk mendefinisikan array persisten yang bertahan. Kami kemudian dapat menetapkan fungsi yang kami buat ke metode array toString, dan tugas-tugas itu juga akan tetap ada. Sekarang, yang harus kita lakukan adalah sederhana +[]pada array, dan tiba-tiba, fungsi kita yang ditentukan kustom akan berjalan. Ini artinya kita bisa menggunakan karakter+=[]untuk memanggil fungsi, dan karena itu fungsi kita dapat memanggil satu sama lain - atau diri mereka sendiri. Ini memberi kita rekursi, yang memberi kita putaran, dan tiba-tiba kita memiliki semua yang kita butuhkan untuk kelengkapan Turing.

Berikut adalah seperangkat fitur yang memberikan Turing-kelengkapan, dan bagaimana mereka diimplementasikan:

• Penyimpanan tanpa batas : array bersarang di penyimpanan konstruktor
• Aliran kontrol : diimplementasikan menggunakan ifdan rekursi:
  • if: mengkonversi boolean menjadi angka, dan indeks menjadi array 2-elemen; satu elemen menjalankan fungsi untuk thencase saat dirender, elemen lainnya menjalankan fungsi untuk elsecase saat stringified
  • Rekursi : merangkai elemen yang sesuai dari penyimpanan konstruktor
• Urutan perintah : [a]+[b]+[c]mengevaluasi a,, bdan ckiri-ke-kanan (setidaknya pada browser yang saya periksa)

Sayangnya, ini cukup tidak praktis; tidak hanya sangat besar mengingat bahwa string harus dibangun karakter-demi-karakter dari prinsip-prinsip pertama, itu juga tidak memiliki cara untuk melakukan I / O (yang tidak harus lengkap Turing). Namun, jika itu berakhir, setidaknya mungkin untuk melihat di penyimpanan konstruktor secara manual setelahnya, jadi itu tidak mungkin untuk men-debug program Anda, dan mereka tidak sepenuhnya tidak komunikatif.

Unary , 1 karakter

0

Pilihan karakter tidak terlalu penting; panjang program mendefinisikan program brainfuck yang ditranslasikannya. Sementara spec mengamanatkan 0karakter, sebagian besar transponder tampaknya tidak memeriksa ini.

vim, 9 8 7 6 karakter

<C-v><esc>1@ad

Kita dapat membangun dan menjalankan program vimscript sewenang-wenang sebagai berikut:

1. Gunakan urutan aa<C-v><C-v>1<esc>dd@1<esc>dddduntuk mendapatkan <C-a>daftar masuk 1.

2. Masuk ke mode insert dengan a, lalu masukkan a, yang akan digunakan untuk masuk kembali ke mode insert di makro nanti.

3. Untuk setiap karakter dalam program vimscript yang diinginkan,

   1. gunakan <C-v><C-v>1<esc>untuk memasukkan urutan literal <C-v>1,

   2. gunakan @1(yaitu <C-a><cr>, di mana final <cr>adalah no-op karena berada di baris terakhir) sebanyak yang diperlukan untuk meningkatkan 1sampai nilai ASCII dari karakter yang diinginkan tercapai,

   3. dan masukkan kembali mode insert dengan a.

4. Hapus baris (bersama dengan trailing newline) ke dalam 1register dengan <esc>dd.

5. Jalankan hasilnya sebagai penekanan tombol vim dengan menggunakan @1, kemudian <esc>dduntuk menghapus baris yang dimasukkan oleh baris baru dari langkah sebelumnya.

6. Jalankan urutan byte yang dihasilkan sewenang-wenang dengan dd@1. Jika dimulai dengan a :, itu akan ditafsirkan sebagai kode vimscript, dan itu akan dijalankan karena mengikuti baris baru dari dd.

Saya tidak yakin ini adalah set karakter minimal, tetapi cukup mudah untuk membuktikan menjadi Turing-lengkap.

Perl, 5 karakter

<>^es

Seperti bahasa scripting lainnya, idenya adalah evalstring arbitrer. Namun, rangkaian karakter kami tidak menyertakan kutipan atau operator gabungan, jadi membangun string arbitrer akan menjadi jauh lebih rumit. Perhatikan bahwa eval^"akan jauh lebih mudah untuk ditangani, tetapi memiliki satu karakter lagi.

Alat utama kami adalah s<^><CODE>ee, yang mengevaluasi CODE, kemudian mengevaluasi hasilnya. Lebih banyak edapat ditambahkan, dengan efek yang diharapkan.

Kami mendapatkan string menggunakan <>, yang merupakan operator glob kecuali saat itu tidak. Karakter pertama tidak boleh <(jika tidak terlihat seperti <<operator), kurung sudut harus seimbang, dan harus ada setidaknya satu karakter non-huruf (selain itu ditafsirkan sebagai operator readline).

Dengan mengaitkan string-string itu bersama-sama, kita dapat memperoleh kombinasi karakter apa pun ^B^V^S(*-/9;<>HJMOY[`\^begqstv, asalkan kita menerima sampah di sekitar (tiga yang pertama adalah karakter kontrol).

Sebagai contoh, misalkan kita ingin mendapatkannya "v99". Salah satu cara untuk mendapatkannya v99adalah "><<" ^ "e>>" ^ "see" ^ "^^^", tetapi kami tidak dapat mewakili string tersebut karena kendala pada <>. Jadi sebagai gantinya, kami menggunakan:

<^<<^>><>>^<^^^^^<>>^<^^^^^^e>^<^^^^^^^>^<^^^^^e>^<^^^^e^>^<e^^es>^<^ee^^>^<^<^^^^^>>^<^<>^^^^>^<^^^^^^^e>^<^^^^^^^^>

Hasil di atas Y9;v99;, yang, ketika eval-ed, menghasilkan hasil yang sama sebagai dataran v99(yaitu, karakter dengan kode ASCII 99).

Dengan demikian kita dapat menggunakan seluruh ^B^V^S(*-/9;<>HJMOY[`\^begqstvrangkaian karakter untuk menghasilkan string arbitrer kita, lalu mengonversinya seperti di atas dan memasukkannya ke dalam s<><CODE>eeeeuntuk mengeksekusinya. Sayangnya, rangkaian karakter ini masih sangat terbatas, tanpa ada cara yang jelas untuk melakukan penggabungan.

Tapi untungnya, itu berisi bintang. Ini memungkinkan kami menulis *b, yang mengevaluasi string "*main::b". Kemudian, *b^<^B[MMH^V^SY>(^ B, ^ V dan ^ S adalah karakter kontrol literal) memberi kita (6, $&);, yang, ketika dievaluasi lagi, mengembalikan nilai variabel kecocokan Perl $&,. Ini memungkinkan kita menggunakan bentuk gabungan terbatas: kita dapat berulang kali menambahkan beberapa hal untuk $_digunakan s<^><THINGS>e, dan kemudian menggunakan s<\H*><*b^<^B[MMH^V^SY>>eeeuntuk eval $_( \Hcocok dengan apa pun kecuali spasi putih horisontal; kita menggunakannya sebagai ganti titik, yang tidak ada di rangkaian karakter kita).

Dengan menggunakan 9-/, kita dapat dengan mudah menghasilkan semua digit. Menggunakan digit,, vdan gabungan, kita dapat menghasilkan karakter arbitrer (vXXX menghasilkan karakter dengan kode ASCII XXX). Dan kita bisa menggabungkannya, sehingga kita bisa menghasilkan string yang arbitrer. Jadi sepertinya kita bisa melakukan apa saja.

Mari kita menulis contoh lengkap. Misalkan kita menginginkan program yang mencetak PID-nya sendiri. Kami mulai dengan program alami:

say$$

Kami mengonversinya menjadi v-notasi:

s<><v115.v97.v121.v36.v36>ee

Kami menulis ulang ini hanya menggunakan ^B^V^S(*-/9;<>HJMOY[`\^begqstv(spasi putih hanya untuk keterbacaan dan tidak mempengaruhi output):

s<^><
    s<^><9*9-9-9-9-9-9>e;
    s<^><v>;
    s<v\H\H><*b^<^B[MMH^V^SY>>eee;
    s<^><9*9-9-9-9-9-9>e;
    s<^><v>;
    s<v\H\H><*b^<^B[MMH^V^SY>>eee;
    s<^><99-99/-9-99/-9>e;
    s<^><v>;
    s<v\H\H\H><*b^<^B[MMH^V^SY>>eee;
    s<^><99-9/9-9/9>e;
    s<^><v>;
    s<v\H\H><*b^<^B[MMH^V^SY>>eee;
    s<^><999/9-9/-9-9/-9-9/-9-9/-9>e;
    s<^><v>;
    s<v\H\H\H><*b^<^B[MMH^V^SY>>eee;
    s<\H*><*b^<^B[MMH^V^SY>>eee;
>eee;

Akhirnya, kami mengonversi program di atas menjadi hanya <>^es: pastebin . Sayangnya, ini crash dengan Perl Excessively long <> operator, tapi itu hanya batasan teknis dan tidak boleh diperhitungkan.

Fiuh, itu cukup perjalanan. Akan sangat menarik untuk melihat seseorang datang dengan 5 karakter yang membuat semuanya lebih sederhana.

EDIT: dengan menggunakan pendekatan yang sedikit berbeda, kita dapat menghindari memukul batas panjang <>. Interpreter brainfuck yang berfungsi penuh hanya dengan menggunakan <>^es: Cobalah online! . Perl otomatis ke <>^estranspiler: pastebin .

Python 2, 7 karakter

exc="%\n

Setiap program Python 2 dapat dikodekan menggunakan 7 karakter ini ( \nadalah baris baru).

Membangun string yang sewenang-wenang

Kita dapat melakukan penggabungan dengan berulang kali menerapkan operator pengganti %pada satu string. Misalnya, jika a=1, b=2, c=3,"%d%%d%%%%d" % a % b % c akan memberi kita string "123". Untungnya, surat-surat dalam execmemberi kita akses ke %xdan %cyang pada dasarnya hex()dan chr(). Dengan %c, kita dapat membuat string apa pun asalkan kita memiliki angka yang diperlukan yang mewakili karakter. Kami kemudian dapat mengeksekusi string ini sebagai kode python menggunakan execkata kunci.

Buat angka

Kami dapat memperoleh akses ke 0dan 1langsung keluar dari kelelawar dengan perbandingan ( ==). Melalui kombinasi angka gabungan dan modulo, dimungkinkan untuk membuat angka 43yang diwakili +dalam ASCII. Ini memungkinkan kita untuk membangun angka yang kita butuhkan untuk kode kita.

Menyatukannya

Saya menghilangkan beberapa detail dalam penjelasan ini karena tidak penting dalam memahami bagaimana program di bawah kendala ini dapat ditulis. Di bawah ini adalah program Python 2 yang saya tulis yang mengubah program python menjadi versi yang secara fungsional setara yang hanya menggunakan 7 karakter ini. Teknik yang digunakan terinspirasi oleh ini pengajuan pada anarki golf oleh k. Beberapa trik sederhana juga digunakan untuk menjaga ukuran program yang dihasilkan dalam batas yang wajar.

import sys

var = {
    43: 'e',
    'prog': 'x', # the program will be stored in this variable
    'template': 'c',
    0: 'ee',
    1: 'ex',
    2: 'ec',
    4: 'xe',
    8: 'xx',
    16: 'xc',
    32: 'ce',
    64: 'cc',
    'data': 'cx', # source program will be encoded here
}

unpacker = 'exec"".join(chr(eval(c))for c in {}.split())'.format(var['data'])

source = sys.stdin.read()
charset = sorted(list(set(source+unpacker)))
codepoints = map(ord, charset)

output = (
    # create template for joining multiple characters
    '{}="%c%%c%%%%c%%%%%%%%c"\n'.format(var['template']) +

    # create 1
    '{0}={1}=={1}\n'.format(var[1], var['template']) +

    # create 0
    '{}={}==""\n'.format(var[0], var['template']) +

    # create 3
    # store it at var[43] temporarily
    (
        'exec"{0}=%x%%x"%{2}%{2}\n' +
        'exec"{0}%%%%%%%%=%x%%x%%%%x"%{1}%{2}%{1}\n'
    ).format(var[43], var[0], var[1]) +

    # create 4
    # this step overwrites the value stored at var[0]
    (
        'exec"{1}=%x%%x"%{0}%{1}\n' +
        'exec"{1}%%%%=%x%%x"%{2}%{0}\n'
    ).format(var[43], var[0], var[1]) +

    # create 43
    'exec"{0}=%x%%x"%{1}%{0}\n'.format(var[43], var[0])
)

# create powers of 2
for i in [2, 4, 8, 16, 32, 64]:
    output += 'exec"{0}={1}%c{1}"%{2}\n'.format(var[i], var[i/2], var[43])

for i, c in enumerate(codepoints):
    # skip if already aliased
    if c in var:
        continue

    # generate a new name for this variable
    var_name = ''
    if i < 27:
        for _ in range(3):
            var_name += 'exc'[i%3]
            i /= 3
    else:
        i -= 27
        for _ in range(4):
            var_name += 'exc'[i%3]
            i /= 3
    var[c] = var_name

    # decompose code point into powers of two
    rem = c
    pows = []
    while rem:
        pows.append(rem&-rem)
        rem -= rem&-rem

    # define this variable
    front = 'exec"{}={}'.format(var[c], var[pows.pop()])
    back = '"'
    for i, p in enumerate(pows):
        front += '%'*(2**i) + 'c' + var[p]
        back += '%' + var[43]
    output += front + back + '\n'

# initialise the unpacker
output += 'exec"""{}=""\n"""\n'.format(var['prog'])
i = 0
length = len(unpacker)
while i < length:
    if (length-i) % 4 == 0:
        # concat 4 characters at a time
        w, x, y, z = [var[ord(unpacker[i+j])] for j in range(4)]
        output += 'exec"{}%c={}%%{}%%{}%%{}%%{}"%{}\n'.format(var['prog'], 
                    var['template'], w, x, y, z, var[43])
        i += 4
    else:
        output += 'exec"""{}%c="%%c"%%{}"""%{}\n'.format(var['prog'],
                    var[ord(unpacker[i])], var[43])
        i += 1

# encode source data
output += var['data'] + '="""'
output += '\n'.join(var[ord(c)] for c in source)
output += '"""\n'

# execute the program
output += 'exec"exec%c{}"%{}'.format(var['prog'], var[32])

print output

Cobalah online

Mathematica, 5 4 karakter

I[]

adalah karakter Unicode penggunaan pribadi , yang bertindak sebagai operator untuk Functionitu memungkinkan Anda menulis literal untuk fungsi yang tidak disebutkan namanya dengan argumen bernama. Karakternya sangat mirip ↦di Mathematica, jadi saya akan menggunakan yang itu untuk sisa jawaban ini untuk kejelasan.

Menggunakan ini, kita dapat menerapkan S, Kdan Icombinators logika combinatory:

I -> II↦II
K -> II↦III↦II
S -> II↦III↦IIII↦II[IIII][III[IIII]]

Salah satu masalah sintaksis dengan ini adalah yang ↦memiliki prioritas sangat rendah yang akan menjadi masalah jika kita mencoba meneruskan argumen ke kombinator ini. Anda biasanya akan memperbaikinya dengan membungkus kombinator Cdalam tanda kurung suka (C), tetapi kami tidak memiliki tanda kurung. Namun, kita dapat menggunakan Idan[] untuk membungkus Cbeberapa sihir lain yang memiliki prioritas cukup tinggi yang dapat kita gunakan nanti:

I[C][[I[[]]I]]

Akhirnya, untuk menulis sebuah aplikasi A x y z(di mana Aadalah combinator "parenthesised" seperti yang ditunjukkan di atas, dan x, y,z mungkin atau mungkin tidak parenthesised, atau mungkin ekspresi yang lebih besar), kita bisa menulis:

A[x][y][z]

Itu meninggalkan pertanyaan tentang bagaimana sebenarnya tanda kurung bekerja. Saya akan mencoba menjelaskannya secara kasar sesuai urutan yang saya buat.

Jadi, yang kita miliki secara sintaksis untuk mengelompokkan sesuatu adalah tanda kurung []. Tanda kurung muncul dalam dua cara di Mathematica. Baik sebagai pemanggilan fungsi f[x], atau sebagai operator pengindeksan f[[i]](yang sebenarnya hanya singkatan untuk Part[f, i]). Secara khusus itu berarti bahwa baik [C]atau [[C]]sintaks yang valid. Kami membutuhkan sesuatu di depannya. Secara teori itu bisa apa saja. Jika kita menggunakan yang Isudah kita miliki kita bisa dapatkan I[C]misalnya. Ini tetap tidak dievaluasi, karena Iitu bukan fungsi yang tidak disadari (ini sama sekali bukan fungsi).

Tapi sekarang kita perlu beberapa cara untuk mengekstrak Clagi, karena kalau tidak, itu tidak akan benar-benar dievaluasi ketika kita mencoba untuk menyampaikan argumen xpadanya.

Di sinilah berguna yang f[[i]]dapat digunakan untuk ekspresi sewenang-wenang f, bukan hanya daftar. Dengan asumsi bahwa fitu sendiri adalah dari bentuk head[val1,...,valn], lalu f[[0]]memberi head, f[[1]]memberi val1, f[[-1]]memberi , valndan seterusnya. Jadi kita perlu untuk mendapatkan 1atau -1mengekstrak Clagi, karena salah satu I[C][[1]]atauI[C][[-1]] mengevaluasi C.

Kita dapat memperoleh 1dari simbol yang tidak ditentukan yang sewenang-wenang seperti x, tetapi untuk melakukan itu, kita memerlukan karakter lain untuk pembagian ( x/xmemberi 1untuk yang tidak ditentukan x). Perkalian adalah satu-satunya operasi aritmatika yang dapat kita lakukan tanpa karakter tambahan (pada prinsipnya), jadi kita memerlukan beberapa nilai yang dapat dikalikan untuk diberikan -1atau 1. Ini akhirnya menjadi alasan mengapa saya secara khusus memilih Ipengidentifikasi kami. Karena Idengan sendirinya adalah simbol bawaan Matematika untuk unit imajiner.

Tetapi yang meninggalkan satu masalah akhir: bagaimana kita benar-benar kalikan Idengan sendirinya? Kita tidak bisa hanya menulis IIkarena itu diurai sebagai simbol tunggal. Kita perlu memisahkan token ini tanpa a) mengubah nilainya dan b) menggunakan karakter baru.

Bit terakhir dari sihir adalah bagian dari perilaku tidak berdokumen: f[[]](atau yang setara Part[f]) adalah sintaks yang valid dan mengembalikan fdirinya sendiri. Jadi alih-alih mengalikan Idengan I, kita mengalikan I[[]]dengan I. Memasukkan tanda kurung menyebabkan Mathematica mencari token baru setelahnya, dan I[[]]Imengevaluasi -1sesuai yang diperlukan. Dan begitulah akhirnya kitaI[C][[I[[]]I]] .

Perhatikan bahwa kami tidak dapat menggunakannya I[]. Ini adalah permohonan fungsi tanpa argumen I, tapi seperti yang saya katakan sebelumnya Ibukan fungsi, jadi ini akan tetap tidak dievaluasi.

Python 2, 8 karakter

exc'%~-0

Karakter-karakter ini memungkinkan terjemahan / eksekusi program Python menggunakan string format dan exec . Meskipun bisa menerjemahkan program apa pun tidak diperlukan untuk kelengkapan Turing, ini adalah karakter paling sedikit yang saya tahu yang menjadikannya TC. Itu sangat kuat hanyalah bonus.

Tanda kutip ganda serta setiap digit selain nol juga dapat digunakan. (Sekarang aku berpikir tentang hal itu, 1pasti akan lebih baik, sehingga program-program yang lebih pendek, karena Anda bisa menggunakan 1, 11dan111 , juga.)

Inilah programnya print:

exec'%c%%c%%%%c%%%%%%%%c%%%%%%%%%%%%%%%%c'%-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~0%-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~0%-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~0%-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~0%-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~0

Cobalah online

Program dasar membutuhkan

exec''

Setiap karakter yang xditambahkan ke program membutuhkan (char - count):

• % - 2**(n-1)
• c - 1
• - - ord(x)*2
• ~ - ord(x)*2
• 0 - 1

Pengecualian untuk hal ini adalah optimasi / jalan pintas tertentu dapat diambil untuk membuat program yang disandikan lebih pendek, seperti menggunakan %'0'untuk karakter 0daripada 48-~ , dll.

Penggunaan praktis (golf AKA): Saya menggunakan taktik ini untuk menyelesaikan tantangan ini tanpa menggunakan karakter handicap tambahan.

Penghargaan untuk daftar karakter dan program encoder: di sini

Untuk informasi tentang menemukan batas bawah pada ukuran program yang dihasilkan (tanpa optimasi), lihat komentar ini .

Jumlah byte yang dibutuhkan naik O(2**n), jadi metode ini tidak disarankan untuk bermain golf. Quine yang menggunakan batasan sumber ini akan sangat panjang.

C (unportable), 24 18 13 karakter

aimn[]={};,1+

Ini mencakup semua program formulir

main[]={<sequence of constants>};

... di mana urutan konstanta (dari bentuk 1 + 1 + 1 ...) berisi representasi kode mesin dari program Anda. Ini mengasumsikan bahwa lingkungan Anda mengizinkan semua segmen memori untuk dieksekusi (tampaknya benar untuk tcc [terima kasih @ Dennis!] Dan beberapa mesin tanpa NX bit). Jika tidak, untuk Linux dan OSX Anda mungkin harus menambahkan kata kunci constdan untuk Windows Anda harus menambahkan#pragma eksplisit menandai segmen sebagai yang dapat dieksekusi.

Sebagai contoh, program berikut yang ditulis dengan gaya di atas mencetak Hello, World!pada Linux dan OSX pada x86 dan x86_64.

main[]={111111111+111111111+11111111+11111111+1111111+1111111+1111111+1111111+1111111+11111+11111+11111+11111+11111+11111+11111+11111+111+11+11+11+11+11+11+1+1,1111111111+11111111+11111111+11111111+11111111+11111111+11111111+11111111+11111111+1111111+1111111+1111111+1111111+1111111+1111111+1111111+111111+11111+11111+11111+11111+11111+11111+1111+1111+1111+111+111+111+111+111+111,1111111111+111111111+111111111+111111111+111111111+111111111+111111111+11111111+11111111+11111111+11111111+11111111+11111111+11111111+11111111+1111111+1111111+111111+111111+111111+111111+11111+11111+11111+1111+1111+1111+1111+1111+1111+1111+1111+111+111+111+111+111+111+111+111+111+11+11+11+11+11+1+1+1+1+1+1+1,1111111111+111111111+111111111+111111111+111111111+111111111+111111111+11111111+11111111+11111111+11111111+11111111+11111111+11111111+11111111+1111111+111111+11111+11111+11111+11111+11111+11111+11111+11111+1111+1111+111+111+111+111+111+111+111+11+11+11+11+11+11+1+1+1+1,111111111+111111111+111111111+111111111+111111111+1111111+1111111+1111111+1111111+111111+111111+1111+1111+1111+1111+1111+1111+111+111+111+111+111+11+11+11+11+1+1+1+1,111111111+111111111+111111111+111111111+111111111+111111111+111111111+111111111+111111111+11111111+11111111+11111111+11111111+11111111+11111111+11111111+1111111+1111111+1111111+1111111+1111111+1111111+1111111+111111+111111+111111+111111+111111+111111+111111+1111+1111+1111+111+111+111+111+111+11+11+11+11+11+11+1+1+1+1+1+1,111111111+111111111+11111111+11111111+11111111+11111111+11111111+11111111+1111111+1111111+1111111+1111111+111111+111111+111111+111111+11111+11111+11111+11111+11111+11111+11111+11111+111+111+111+111+111+111+11+11+11+11+11+11+11+1,1111111111+111111111+111111111+111111111+11111111+11111111+11111111+11111111+1111111+1111111+1111111+111111+111111+111111+111111+111111+111111+111111+111111+11111+11111+11111+11111+11111+1111+1111+1111+1111+1111+1+1+1+1+1,1111111111+111111111+111111111+111111111+111111111+111111111+111111111+1111111+1111111+1111111+1111111+1111111+111111+111111+111111+11111+11111+11111+11111+1111+1111+111+111+111+111+111+111+111+111+111+11+11+11+11+11+1+1+1+1+1+1+1+1+1,1111111111+1111111111+111111111+111111111+111111111+111111111+111111111+111111111+11111111+11111111+11111111+11111111+11111111+11111111+1111111+1111111+111111+111111+111111+111111+11111+11111+1111+1111+1111+1111+1111+1111+1111+111+111+111+111+111+11+11+1+1+1+1+1,1111111111+111111111+111111111+111111111+111111111+111111111+111111111+111111111+111111111+111111111+11111111+11111111+11111111+11111111+1111111+1111111+1111111+1111111+111111+111111+111111+111111+111111+111111+111111+111111+11111+11111+11111+11111+1111+1111+1111+1111+1111+111+11+1+1+1+1+1,1111111111+1111111111+111111111+111111111+111111111+111111111+111111111+111111111+111111111+111111111+111111111+11111111+11111111+11111111+11111111+1111111+1111111+1111111+1111111+1111111+111111+111111+111111+11111+11111+11111+11111+11111+11111+11111+11111+11111+111+111+111+111+1+1+1+1+1+1+1,1111111111+1111111111+1111111111+111111111+111111111+111111111+111111111+111111111+111111111+111111111+111111111+11111111+11111111+11111111+11111111+11111111+11111111+1111111+1111111+1111111+1111111+1111111+111111+111111+111111+111111+11111+11111+1111+1111+111+111+111+111+111+111+111+111+111+11+11+11+11+11+11+1+1+1,1111111111+111111111+111111111+111111111+1111111+1111111+1111111+111111+111111+111111+111111+111111+111111+111111+1111+1111+1111+1111+1111+1111+1111+1111+111+111+111+111+111+111+111+111+111+1+1+1+1+1+1,111111+111111+11111+11111+11111+11111+11111+11111+11111+1111+1111+1111+1111+1111+1111+1111+1111+111+111+111+11+11+11+11+11+11+11+11+11+11,11111111+11111111+11111111+11111111+11111111+11111111+11111111+1111111+1111111+1111111+1111111+1111111+1111111+111111+111111+111111+11111+11111+11111+11111+11111+11111+11111+11111+1111+1111+111+111+111+111+111+111+11+11+11+11+11+11+11+1+1+1,111111111+111111111+111111111+111111111+111111111+111111111+111111111+11111111+11111111+11111111+11111111+1111111+1111111+1111111+1111111+1111111+111111+111111+111111+11111+11111+11111+11111+11111+11111+11111+11111+1111+1111+111+111+111+11+11+11+1,111111111+111111111+11111111+11111111+1111111+1111111+1111111+1111111+1111111+1111111+111111+111111+111111+111111+111111+11111+11111+11111+11111+11111+11111+11111+11111+11111+1111+1111+111+11+11+1+1+1+1+1,11111+11111+11111+11111+1111+1111+1111+1111+111+111+111+111+111+111+111+111+111+11+11+11+1+1+1+1+1};

Cobalah online!

Retina , 6 karakter

$%`{¶

Seperti halnya linefeeds (0x0A).

Di satu sisi saya terkejut bahwa saya bisa mendapatkannya serendah ini. Di sisi lain, saya sangat tidak senang dengan dimasukkannya %¶. Masing-masing $`{digunakan kembali untuk dua atau bahkan tiga tujuan, tetapi %¶ bersama-sama hanya melayani satu tujuan. Itu membuat mereka tampak agak boros dan sedikit merusak keanggunan pendekatan. Saya harap ada cara untuk mengalahkan konstruksi ini.

Aktif untuk buktinya. Saya akan menjelaskan cara sederhana untuk menerjemahkan sistem tag siklik ke Retina menggunakan karakter di atas.

Pertama, kami akan menggunakan `dan {untuk alfabet biner alih-alih 0dan 1. Ini nyaman, karena mereka tidak perlu melarikan diri dalam regex, tetapi mereka memiliki makna baik untuk Retina atau dalam sintaksis substitusi. Saya menggunakan `untuk 0dan {untuk 1, tetapi pilihan ini arbitrer. Selanjutnya, kita akan membalikkan string (dan produksi) dalam memori, karena bekerja dengan karakter terakhir memungkinkan kita menggunakan $dan $`alih-alih ^dan$' , memaksimalkan penggunaan kembali karakter.

Jika kata awal dilambangkan dengan Sdan produksi ith (terbalik) dipanggil , program yang dihasilkan akan terlihat seperti ini:pi

S
{`

{$
¶p1$%``
``$

{$
¶p2$%``
``$

{$
¶p3$%``
``$

...

Konstruksi ini tak terhindarkan tumbuh dalam memori setiap kali produksi diterapkan, dan itu tidak mungkin berakhir - pada kenyataannya, pada titik di mana sistem tag siklik akan berakhir (ketika string kerja menjadi kosong), perilaku program Retina yang dihasilkan menjadi pada dasarnya tidak terdefinisi.

Mari kita lihat apa yang dilakukan oleh program:

S

Kita mulai dengan menginisialisasi string yang berfungsi ke kata awal.

{`

Ini membungkus sisa program dalam sebuah yang berjalan sampai gagal mengubah string yang dihasilkan (hei, deteksi loop tak terbatas bawaan tak terbatas ...). Dua linefeed tidak benar-benar diperlukan, tetapi mereka memisahkan loop lebih jelas dari masing-masing produksi. Sisa dari program berjalan melalui masing-masing produksi, dan karena loop kami secara efektif memprosesnya secara berulang berulang.

Setiap produksi diproses oleh dua tahap. Pertama-tama kita berurusan dengan kasus bahwa simbol terkemuka (atau dalam kasus kita tertinggal) adalah {, dalam hal ini kita menggunakan produksi:

{$
¶pi$%``

Regex hanya cocok jika string berakhir { . Jika demikian, kami menggantinya dengan:

• Linefeed ( ¶). Kami hanya akan bekerja dengan baris terakhir dari string yang bekerja, jadi ini secara efektif membuang string yang bekerja sejauh ini (itulah sebabnya penggunaan memori dari program ini akan tumbuh dan tumbuh).
• Produksi saat ini (pi ), yang dengan ini kami tambahkan terlebih dahulu ke string yang berfungsi (di mana sistem tag siklik menambahkannya).
• String kerja yang tersisa sebelumnya ( $%`). Inilah sebabnya mengapa kita harus memasukkan ¶: $%`mengambil semua yang tersisa dari pertandingan, tetapi hanya pada baris yang sama. Karenanya, ini tidak melihat semua sampah yang kami tinggalkan dari produksi sebelumnya. Trik ini memungkinkan kita mencocokkan sesuatu di akhir string kerja untuk memasukkan sesuatu di awal string kerja, tanpa harus menggunakan sesuatu seperti(.+) dan $1yang secara signifikan akan meledakkan jumlah karakter yang kita butuhkan.
• Sebuah backtick tunggal ( `). Ini secara efektif menggantikan {( 1-simbol) yang kami cocokkan dengan `( 0-simbol) sehingga tahap berikutnya tidak perlu tahu apakah kami sudah memproses produksi saat ini atau tidak.

Bagian kedua dari setiap produksi kemudian menjadi kasus sepele di mana produksi dilewati:

``$

Kami cukup menghapus trailing `. Alasan kita membutuhkan dua `di baris pertama adalah bahwa Retina menganggap backtick pertama sebagai pembagi antara konfigurasi dan regex. Ini hanya memberinya konfigurasi kosong sehingga kita dapat menggunakan backticks di regex itu sendiri.

Java 7, 18 17 karakter

\bcdefu0123456789

Semua kode sumber java dapat dikurangi menjadi titik kode unicode. "a" tidak diperlukan karena hanya digunakan untuk*:jJzZ . Asterisk digunakan untuk perkalian atau memblokir komentar. Perkalian hanyalah penambahan berulang dan Anda dapat menggunakan komentar satu baris saja (atau hanya menghilangkannya). Usus besar digunakan untuk operator ternary, yang Anda dapat menggunakan pernyataan if untuk gantinya, dan foreach loop, yang dapat diganti dengan normal untuk loop. j dan z bukan bagian dari kata kunci apa pun di java.

Mencoba untuk menghapus karakter lain mengharuskan kami untuk menambahkan setidaknya satu dari karakter yang diperlukan dalam Java boiler plate class a{public static void main(String[]a){}}. Lihat di bawah:

1 -> a (which has already been removed)
2 -> r (required for "String")
3 -> S (required for "String")
4 -> t (required for "static")
5 -> S (required for "String")
6 -> v (required for "void")
7 -> g (required for "String")
8 -> ( (required for "main(String[]a)"
9 -> i (required for "static")
b -> { (required for "class a{")
c -> l (required for "class")
d -> } (required for "(String[]a){}}")
e -> n (required for "main")
f -> o (required for "void")

Berikut ini contoh dengan program Hello World Cobalah secara online!

Java 8, 16 karakter

\bdefu0123456789

Terima kasih kepada ais523 untuk menunjukkan ini. Java 8 memungkinkan antarmuka untuk memiliki metode statis yang berarti kita dapat menjatuhkan "c" karena kita tidak memerlukannya untuk "l" di "kelas". "C" digunakan untuk ,<lL\|jadi kita akhirnya kehilangan fungsionalitas java sedikit lebih daripada ketika kita menghapus "a" tapi kita masih memiliki cukup untuk menjadi turing lengkap. Cobalah online!

Labirin , 5 karakter

~{}

Ditambah umpan baris (0x0A) dan spasi (0x20).

Saya akan membuat sketsa bukti dalam bentuk pengurangan dari Smallfuck (varian Brainfuck yang berkurang yang menggunakan sel 1-bit). Perhatikan bahwa Smallfuck sendiri bukan Turing-complete karena bahasa menetapkan bahwa rekamannya harus terbatas, tetapi kita akan menganggap varian Smallfuck dengan tape tak terbatas, yang kemudian akan menjadi Turing-complete (karena Labyrinth tidak memiliki memori) pembatasan oleh desain).

Satu invarian penting dalam pengurangan ini adalah bahwa setiap program (atau subprogram) akan menghasilkan program Labirin (atau subprogram) yang dimulai dan berakhir pada baris yang sama, dan merentang jumlah kolom yang genap.

Labirin memiliki dua tumpukan yang awalnya diisi dengan jumlah tak terbatas (implisit) dari 0s. {dan }menggeser nilai teratas di antara tumpukan ini. Jika kita menganggap bagian atas tumpukan utama sebagai "sel" saat ini, maka kedua tumpukan ini dapat dilihat sebagai dua bagian setengah tak terbatas dari pita tak terbatas yang digunakan oleh Smallfuck. Namun, akan lebih mudah untuk memiliki dua salinan dari masing-masing nilai kaset di tumpukan, untuk memastikan invarian yang disebutkan di atas. Oleh karena itu <dan >akan diterjemahkan ke {{dan }}, masing-masing (Anda dapat menukar mereka jika Anda mau).

Alih-alih membiarkan nilai sel 0dan 1, kami menggunakan 0dan -1, yang dapat kami beralih antara dengan ~(negasi bitwise). Nilai yang tepat tidak masalah untuk tujuan Turing-kelengkapan. Kita harus mengubah kedua salinan nilai pada tumpukan, yang memberi kita terjemahan yang panjang-panjang lagi: *menjadi ~}~{.

Yang meninggalkan perintah aliran kontrol []. Labirin tidak memiliki aliran kontrol eksplisit, melainkan aliran kontrol ditentukan oleh tata letak kode. Kami membutuhkan spasi dan umpan garis untuk melakukan tata letak itu.

Pertama, perhatikan itu ~~adalah no-op, karena keduanya ~secara efektif membatalkan. Kita bisa menggunakan ini untuk memiliki jalur panjang yang sewenang-wenang dalam kode, asalkan panjangnya genap. Kita sekarang dapat menggunakan konstruksi berikut untuk menerjemahkan AA[BB]CCke Labyrinth (Saya menggunakan huruf ganda sehingga ukuran setiap potongan di Labyrinth genap, seperti yang dijamin oleh yang lain):

      ~~~~
      ~  ~~~
AA~~..~~~~ ~CC
   ~     ~
   ~     ~
   ~     ~
   ~~~BB~~

Di sini, ..adalah nomor ~yang cocok yang cocok dengan lebar BB.

Sekali lagi, perhatikan bahwa lebar konstruksi tetap rata.

Kita sekarang dapat melihat bagaimana loop ini bekerja. Kode dimasukkan melalui AA. Yang pertama ~~tidak melakukan apa-apa dan memungkinkan kita mencapai persimpangan. Ini kira-kira sesuai dengan [:

• Jika nilai sel saat ini adalah nol, IP terus lurus ke depan, yang akhirnya akan dilewati BB. Bagian ..ini masih no-op. Kemudian kami mencapai satu ~di persimpangan lain. Kita sekarang tahu bahwa nilai saat ini adalah nol, sehingga IP mengambil belokan utara. Ia berputar di tikungan di bagian atas, hingga mencapai persimpangan lain setelah enam ~. Jadi pada saat itu nilai saat ini masih non-nol dan IP mengambil belokan lagi untuk bergerak ke timur menuju CC. Perhatikan bahwa ketiganya ~sebelum CCmengembalikan nilai saat ini 0, sebagaimana seharusnya ketika loop dilewati.
• Jika nilai sel saat ini di awal loop adalah nol, IP akan berbelok ke selatan. Ini berjalan enam lebih ~sebelum mencapai BB(yang tidak melakukan apa-apa), dan kemudian enam ~sebelum mencapai persimpangan berikutnya. Ini kira - kira sesuai dengan ].
  • Jika sel saat ini nol, IP terus bergerak ke utara. Berikutnya ~membuat nilai non-nol, sehingga IP mengambil persimpangan kedua ini, yang menggabungkan lintasan dengan kasus bahwa loop dilewati sepenuhnya. Sekali lagi, ketiga ~mengembalikan nilai ke nol sebelum mencapai CC.
  • Jika sel saat ini adalah nol, IP mengambil belokan ke barat. Ada ~sebelum persimpangan berikutnya, yang berarti bahwa pada titik ini nilai saat ini adalah nol sehingga IP terus bergerak ke barat. Kemudian akan ada jumlah ganjil ~sebelum IP mencapai persimpangan awal lagi, sehingga nilainya dikembalikan -1dan IP bergerak ke selatan ke iterasi berikutnya.

Jika program berisi loop, maka yang pertama AAperlu diperluas ke bagian atas program sehingga IP menemukan sel yang tepat untuk memulai:

~     ~~~~
~     ~  ~~~
AA~~..~~~~ ~CC
   ~     ~
   ~     ~
   ~     ~
   ~~~BB~~

Itu itu. Perhatikan bahwa program yang dihasilkan dari pengurangan ini tidak akan pernah berakhir, tetapi itu bukan bagian dari persyaratan kelengkapan Turing (pertimbangkan Aturan 101 atau Fractran).

Akhirnya, kita dibiarkan dengan pertanyaan apakah ini optimal. Dalam hal karakter beban kerja, saya ragu bahwa itu mungkin untuk melakukan lebih baik dari tiga perintah. Saya bisa melihat konstruksi alternatif berdasarkan mesin Minsky dengan dua register, tetapi itu akan membutuhkan =()atau =-~, hanya memiliki satu perintah stack-manipulation tetapi kemudian dua perintah aritmatika. Saya akan senang terbukti salah dalam hal ini. :)

Adapun perintah tata letak, saya percaya bahwa umpan baris diperlukan, karena aliran kontrol yang berguna tidak mungkin pada satu baris. Namun, ruang secara teknis tidak diperlukan. Secara teori dimungkinkan untuk membuat konstruksi yang mengisi seluruh grid dengan ~{}(atau =()atau =-~), atau menggunakan tata letak yang tidak rata di mana garis tidak semuanya sama panjang. Namun, menulis kode seperti itu sangat sulit, karena Labyrinth kemudian akan memperlakukan setiap sel sebagai persimpangan dan Anda harus benar-benar berhati-hati agar kode tidak bercabang saat Anda tidak menginginkannya. Jika ada yang bisa membuktikan atau menyangkal apakah menghilangkan ruang itu mungkin untuk Turing-kelengkapan, saya akan dengan senang hati memberikan hadiah yang cukup besar untuk itu. :)

Haskell, 5 7 karakter

()\->=;

Sebagai bahasa fungsional, Haskell tentu saja memiliki lambda, jadi mensimulasikan kalkulus lambda itu mudah. Sintaks untuk lambdas adalah jadi kita membutuhkan setidaknya karakter . Selain itu, kita membutuhkan jumlah variabel simbol yang tidak terbatas untuk dapat membangun ekspresi lambda yang sewenang-wenang. Untungnya kita tidak perlu karakter baru untuk ini, karena , , , ..., semua nama variabel yang valid. Sebenarnya setiap kombinasi tanda kurung di dalam adalah nama variabel yang valid, dengan pengecualian hanya dan , yang dicadangkan untuk ekspresi lambda, dan , yang memulai komentar baris.(\variable->body)argument()\->
(>)(>>)(>>>)\->\->--

Contoh:

• S = (\(>)(\\)(-)->(>)(-)((\\)(-)))ketik ke(t2 -> t -> t1) -> (t2 -> t) -> t2 -> t1
• K = (\(>)(-)->(>))ketik ket -> t1 -> t
• I = (\(>)->(>))ketik ket -> t

Sunting: Namun, seperti yang ditunjukkan ais523 dalam komentar, konstruksi ini mengimplementasikan kalkulus lambda yang diketik , yang dengan sendirinya tidak menyelesaikan-Turing karena tidak memiliki kemampuan untuk memasukkan loop tak terbatas. Untuk memperbaikinya, kita memerlukan beberapa fungsi yang melakukan rekursi. Sejauh ini kami menggunakan lambda tanpa nama, yang tidak dapat menyebut diri mereka sendiri, karena, well, mereka tidak memiliki nama. Jadi kita harus menambahkan karakter =dan ;mengimplementasikan fixfungsi:

(>)=(\(-)->(-)((>)(-)));   -- equivalent to: f =(\ x -> x ( f  x ));

Dengan deklarasi ini kalkulus lambda kami menjadi Turing lengkap, namun setelah ditambahkan =dan ;, kami tidak perlu lambda lagi, seperti yang Anda lihat dalam jawaban nimi yang menggunakan adil ()=;.

CJam, 3 karakter

Dihapus )sesuai saran Martin Ender

'(~

Mirip dengan Python yang diberikan sebagai contoh.

Menggunakan '~ Anda dapat memperoleh ~karakter. Kemudian menggunakan (, Anda dapat mengurangi untuk mendapatkan karakter apa pun yang Anda inginkan ( ~adalah karakter ASCII yang terakhir dicetak). ~eval string apa pun sebagai kode CJam normal. String dapat dibangun dengan memperoleh karakter [(melalui decrementing ~), mengevaluasinya, menempatkan beberapa urutan karakter lain, kemudian mengevaluasi karakter tersebut ]. Melalui ini, Anda dapat membangun dan menjalankan program CJam hanya menggunakan tiga karakter ini.

Menghitung 2 + 2 hanya menggunakan '(~

Brain-Flak , 6 karakter

(){}[]

Brain-Flak adalah bahasa minimalis dengan hanya 8 karakter yang tersedia. Namun dapat dibuktikan bahwa ada subset Brain-Flak yang juga Turing lengkap hanya menggunakan 6 karakter.

Hal pertama yang akan kita lakukan adalah menerapkan Mesin Minsky dengan hanya satu tumpukan Brain-Flak. Jika kita dapat membuktikan bahwa Mesin Minsky dimungkinkan dengan hanya satu tumpukan, kita dapat menunjukkan bahwa Brain-Flak Turing lengkap tanpa<> dan []nilads. Ini tidak akan menyimpan karakter apa pun segera tetapi akan di masa depan ketika kami menunjukkan bahwa <...>tidak perlu.

Mesin Minsky adalah jenis otomatisasi lengkap Turing yang memiliki jumlah register tak terbatas dan dua instruksi terbatas:

• Tambahkan daftar

• Jika pengurangan bukan nol transisi ke instruksi yang ditentukan

Untuk mengatur struktur goto di Brain-Flak kita dapat menggunakan potongan berikut:

(({}[()])[(())]()){(([({}{})]{}))}{}{(([({}{}(%s))]{}))}{}

Ini akan mengurangi konter dan berjalan %sjika nol. Sekelompok ini dirantai bersama-sama akan memungkinkan kita untuk meletakkan nomor pada tumpukan yang akan menunjukkan baris mana yang ingin kita goto. Masing-masing akan mengurangi bagian atas tumpukan tetapi hanya satu dari mereka yang benar-benar akan menjalankan kode.

Kami menggunakan ini sebagai pembungkus untuk semua instruksi Mesin Minsky kami.

Menambah register tertentu cukup mudah tanpa mengganti tumpukan. Itu dapat dicapai dengan rumus string ini:

"({}<"*n+"({}())"+">)"*n

Misalnya untuk menambah register ke-3 kita akan menulis kode berikut:

({}<({}<({}<({}())>)>)>)

Sekarang kita hanya perlu mengimplementasikan operasi kedua. Memeriksa apakah angka nol cukup sederhana di Brain-Flak:

(({})){(<{}%s>)}{}

hanya akan mengeksekusi %sjika TOS nol. Dengan demikian kita dapat melakukan operasi kedua.

Karena Mesin Minsky adalah Turing lengkap Brain-Flak juga Turing lengkap tanpa menggunakan <>dan[] operasi.

Namun kami belum mengurangi jumlah karakter karena <...>dan [...]masih digunakan. Ini dapat diatasi dengan penggantian sederhana. Karena <...>sebenarnya sama dengan [(...)]{}dalam semua kasus. Jadi Brain-Flak adalah Turing lengkap tanpa menggunakan karakter <dan >(ditambah semua no-ops).

> <> , 3 karakter

> <> dapat dilakukan dalam 3 dengan 1p-, yang dilakukan:

1          Push 1
p          Pop y, x, c and put the char c in cell (x, y) of the codebox
-          Subtraction: pop y, x and push x-y

pmemberikan refleksi, memodifikasi kode sumber 2D dengan menempatkan karakter ke dalam kotak kode. Dengan 1-, Anda dapat memasukkan nomor apa saja ke tumpukan karena 1-kurangi satu dan 111-1--( x-(1-1-1) = x+1) tambahkan satu.

Setelah semua 1p-perintah dieksekusi, penunjuk instruksi membungkus, memungkinkannya untuk mengeksekusi kode "nyata".

Contoh program yang menghitung angka Fibonacci (dari jawaban ini ) adalah:

111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--11-11-p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1--11-p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1-1--11-p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1-1-1--11-p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1-1-1-1--11-p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--11-1p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--11p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1--1p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1-1--1p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1-1-1--1p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1-1-1-1--1p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1-1-1-1-1--1p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1-1-1-1-1-1--1p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1-1-1-1-1-1-1--1p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1-1-1-1-1-1-1-1--1p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1-1-1-1-1-1-1-1-1--1p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1-1-1-1-1-1-1-1-1-1--1p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1-1-1-1-1-1-1-1-1-1-1--1p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1-1-1-1-1-1-1-1-1-1-1-1--1p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1-1-1-1-1-1-1-1-1-1-1-1-1--1p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1-1-1-1-1-1-1-1-1-1-1-1-1-1--1p

Cobalah online! Setelah semua 1p-perintah dieksekusi, kotak kode akan terlihat seperti ini:

01aa+v1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1- ...
@+&1->:?!;&:nao:

Kecuali semuanya setelah vpada baris pertama, ini adalah program Fibonacci> standar>.

bash, 9 karakter

01456\$ '

Bash memiliki sintaks $'\nnn'untuk memasukkan karakter dengan nilai ascii oktal mereka. Kita dapat memasukkan evalperintah dalam format ini sebagai $'\145\166\141\154'. Kami pertama-tama mengubah hasil yang diinginkan menjadi nilai oktal. Kami kemudian mengonversi nilai oktal apa pun menggunakan angka selain 0, 1, 4, 5, dan 6 menjadi ekspresi yang mengevaluasi nilai oktal tersebut menggunakan $(())dan mengurangi, menambahkan a evalke depan. Pada langkah terakhir kami, kami menambahkan yang lain evaldan mengonversi tanda kurung dan tanda minus menjadi nilai oktal mereka. Dengan menggunakan metode ini kita dapat menjalankan perintah bash apa pun, sehingga bagian ini selesai.

Contoh:

dc menjadi

$'\144\143' yang menjadi

$'\145\166\141\154' \$\'\\144\\$((144-1))\' yang menjadi

$'\145\166\141\154' $'\145\166\141\154' $'\$\\\'\\\\144\\\\$\050\050144\0551\051\051\\\''

Kejadian , 2 karakter

Tidak masalah dua karakter yang Anda pilih; kombinasi dari dua oktet adalah Turing-complete dalam Insiden.

Sebenarnya membuktikan ini jauh lebih sulit daripada yang Anda harapkan, dan pada saat penulisan, halaman diskusi tentang Esolang tentang Insiden dikhususkan untuk masalah tersebut. Saya akan mencoba memberikan ringkasan bukti paling sederhana yang diketahui di bawah ini.

Sebelum buktinya, beberapa latar belakang. Insiden menyimpulkan token yang digunakan dalam program dengan melihat sumber (token adalah string yang muncul tepat tiga kali dalam sumber, bukan substring token lain, dan tidak tumpang tindih dengan token potensial lain). Dengan demikian, setiap program dapat dikonversi untuk menggunakan hampir semua set karakter dengan mengubah apa tokennya; bahasa Turing-complete (dan memiliki kelengkapan untuk I / O, juga!), meskipun sangat sulit untuk diprogram, jadi "semua" yang Anda butuhkan adalah metode penyandian token sehingga mereka bekerja hanya dengan dua karakter.

Dan sekarang, inilah ringkasan buktinya (yang ditemukan oleh Ørjan, matematikawan Esolang). Idenya adalah bahwa kita mengkodekan token menggunakan dua salinan dari satu karakter (katakanlah 1) di lautan besar karakter lainnya (katakanlah 0). Jarak antara 1s berbeda untuk setiap token, tetapi selalu merupakan kelipatan dari 4. Kemudian untuk bantalan di antara token, kami menggunakan daftar tambahan 0s dengan a 1di tengah, tetapi jumlah 0s di setiap sisi 1adalah tidak kelipatan dari 4, melainkan nomor unik untuk kejadian khusus program yang tidak muncul di tempat lain dalam program ini. Itu artinya masing-masing1 ...1di dalam padding hanya dapat muncul dua kali, jadi tidak akan menjadi bagian dari token; masing-masing token yang dimaksud mengandung tepat 1s, dan tidak ada token palsu yang bisa memuat lebih dari satu 1. Kemudian kami hanya menambahkan beberapa padding ke samping untuk menghapus semua token yang mungkin berisi satu dengan menambahkan setidaknya empat salinannya.1 atau nol1

Retina , 3 karakter

{`

dan baris baru.

Pertama, kita perlu baris baru untuk dapat melakukan pergantian (diperlukan kecuali jika kita ingin mencocokkan seluruh program menjadi satu regex, yang akan membutuhkan lebih banyak karakter); dan `dan {merupakan cara paling intensif karakter untuk melakukan loop. Ternyata kita tidak butuh yang lain.

Bahasa target kami untuk diterapkan adalah varian deterministik Thue (nondeterminisme tidak diperlukan untuk kelengkapan Turing; mungkin untuk menulis program Thue untuk bekerja dengan benar terlepas dari urutan evaluasi mana yang digunakan). Ide dasarnya adalah untuk mengkompilasi pattern::=replacementke

`pattern
replacement

(yang merupakan terjemahan langsung dari Thue Thue; sebagai alternatif, jika Anda tahu Retina tetapi bukan Thue, Anda dapat menggunakannya sebagai metode untuk mempelajari cara Thue bekerja); sebagai pengecualian, pola yang paling pertama didahului oleh {`sebagai gantinya (untuk menempatkan seluruh program ke dalam satu lingkaran; Program-programnya terus berjalan sampai tidak ada lagi penggantian yang mungkin, dan ini menyebabkan Retina bekerja dengan cara yang sama).

Tentu saja, ini berarti bahwa kita perlu membuktikan Thue Turing-lengkap dengan adil {dan `dalam pola dan penggantian, tetapi itu cukup sederhana; kita mengganti karakter dengan kode ascii n dengan `, n +1 {, dan lainnya `. Jelas tidak mungkin bagi suatu pola untuk cocok di mana saja tetapi pada batas karakter, jadi ini pada akhirnya akan melakukan hal yang sama dengan program aslinya.

Brachylog , 5 karakter

~×₁↰|

Subset karakter ini memungkinkan kita untuk mengimplementasikan versi Fractran di mana satu-satunya angka yang dapat muncul adalah produk dari repunit (yaitu produk dari angka yang dapat ditulis dalam desimal hanya menggunakan angka 1). ~×(dengan integer sebagai subskrip) membagi nilai saat ini dengan integer itu, tetapi hanya jika itu membagi dengan tepat (jika tidak "gagal" dan mencari case lain untuk dijalankan; |pisahkan case). ×mari kita gandakan dengan integer. Jadi menggunakan ~×₁|kita dapat mengimplementasikan satu langkah dari eksekusi Fractran. Kemudian ↰mari kita berulang, menjalankan seluruh program lagi pada nilai saat ini yang baru. Berikut adalah contoh program Fractran yang sangat sederhana ( 11111111111111111111111/111) yang diterjemahkan ke Brachylog.

Jadi, apakah Turing ini lengkap? Yang kita butuhkan untuk membuat Fractran Turing lengkap adalah jumlah bilangan prima yang cukup besar (cukup untuk menulis penerjemah untuk bahasa lengkap Turing di Fractran sendiri). Ada lima yang terbukti dan empat yang didugamembayar kembali bilangan prima, di samping, sangat mungkin, yang belum ditemukan. Itu sebenarnya lebih dari yang kita butuhkan dalam hal ini. Program memeriksa kemungkinan dari kiri ke kanan, sehingga kita dapat menggunakan satu prime sebagai penunjuk instruksi, dan dua lagi sebagai penghitung, menunjukkan kelengkapan Turing dengan hanya tiga bilangan prima (hal yang baik juga, karena ia memungkinkan kita menggunakan pembayaran dengan 2, 19 , dan 23 digit, tanpa harus menggunakan ganti rugi yang terbukti tapi sangat mengganggu dengan 317 atau 1031 digit, yang akan membuat kode sumber cukup sulit untuk ditulis). Itu memungkinkan untuk mengimplementasikan mesin Minsky dengan dua penghitung (cukup untuk Turing-kelengkapan).

Begini cara kompilasi bekerja secara khusus. Kami akan menggunakan dua perintah berikut untuk implementasi mesin Minsky kami (ini dikenal Turing selesai), dan setiap perintah akan memiliki integer sebagai label:

• Label L: Jika penghitung {A atau B} adalah nol, goto X. Jika tidak, kurangi dan goto Y.
• Label L: Penghitung kenaikan {A atau B}, lalu goto Z.

Kami memilih perintah mana yang harus dijalankan melalui menempatkan kekuatan 11 di penyebut, kekuatan tertinggi terlebih dahulu; eksponen 11 adalah label perintah. Dengan begitu, fraksi pertama yang cocok akan menjadi perintah yang sedang dieksekusi (karena yang sebelumnya tidak dapat dibagi dengan semua 11-an). Dalam kasus perintah pengurangan, kami juga menempatkan faktor 111111111111111111111 atau 11111111111111111111111 dalam penyebut, masing-masing untuk counter A atau B, dan menindaklanjutinya dengan perintah lain tanpa faktor itu; case "decrement" akan diimplementasikan oleh perintah pertama, case "zero" oleh yang kedua. Sementara itu, "goto" akan ditangani oleh kekuatan 11 yang sesuai dalam pembilang, dan "peningkatan" melalui faktor 1111111111111111111 atau 11111111111111111111111 dalam pembilang.

Befunge-98, 3 karakter

Sejauh yang saya tahu, Befunge-98 seharusnya selesai, jadi kita hanya perlu menunjukkan bagaimana program Befunge-98 dapat dihasilkan hanya dengan menggunakan tiga karakter. Solusi awal saya mengandalkan empat karakter berikut:

01+p

Kita bisa mendapatkan bilangan bulat positif ke tumpukan dengan menambahkan beberapa 1nilai bersama dengan +perintah, dan untuk nol kita cukup gunakan 0. Setelah kami memiliki kemampuan untuk menekan nomor yang diinginkan, kami dapat menggunakanp (put) untuk menulis nilai ASCII apa pun ke lokasi mana pun di arena bermain Befunge.

Namun, seperti yang Sp3000 tunjukkan, Anda sebenarnya bisa bertahan hanya dengan tiga karakter:

1-p

Setiap angka negatif dapat dihitung dengan memulai dengan 1dan kemudian berulang kali mengurangkan 1(misalnya, -3 akan menjadi 11-1-1-1-). Maka setiap angka positif dapat diwakili dengan mengurangi 1-n dari 1, di mana 1-n adalah angka negatif yang sudah kita ketahui bagaimana menangani (misalnya, 4 = 1 - (- 3), yang akan menjadi111-1-1-1-- ).

Dengan demikian kita dapat menggunakan tiga karakter kita untuk menulis sejenis bootloader yang secara perlahan menghasilkan kode aktual yang ingin kita jalankan. Setelah pemuat ini selesai dieksekusi, pemuat ini akan membungkus ke awal baris pertama dari playfield, yang pada saat itu harus memegang awal kode baru yang kami buat.

Sebagai contoh, inilah bootloader yang menghasilkan kode Befunge yang diperlukan untuk menjumlahkan 2 + 2 dan mengeluarkan hasilnya: 22+.@

Dan untuk contoh yang sedikit lebih rumit, ini adalah "Hello World": "!dlroW olleH"bk,@

Ruby, 8 karakter

eval"<1+

Terinspirasi oleh jawaban Python

Bagaimana itu bekerja

• eval dapat digunakan untuk mengeksekusi string arbitrer.
• "<1+ adalah sekumpulan karakter minimum yang diperlukan untuk membangun string apa pun

String dalam ruby ​​dapat dibuat menggunakan string kosong sebagai titik awal, dan menambahkan karakter ascii ke dalamnya, jadi misalnya:

eval ""<<111+1<<11+11+11+1<<111<<11+11+11+1

sebenarnya setara dengan

eval ""<<112<<34<<111<<34

yang mengevaluasi string

p"o"

OCaml, 9 karakter

fun->()`X

Karakter-karakter ini cukup untuk mengimplementasikan Kalkulus Combinator SKI di OCaml. Khususnya kita dapat menghindari penggunaan ruang dengan tanda kurung yang cukup. Sayangnya ekspresi lambda di OCaml memerlukan funkata kunci sehingga solusi yang lebih singkat tidak mungkin. Huruf yang sama dapat digunakan untuk membangun nama variabel yang berubah-ubah jika diinginkan ekspresi lambda yang kompleks

S Combinator:

fun(f)(u)(n)->f(n)(u(n)) dengan tipe ('a -> 'b -> 'c) -> ('a -> 'b) -> 'a -> 'c

K Combinator:

fun(f)(u)->u dengan tipe 'a -> 'b -> 'b

Saya Combinator:

fun(f)->f dengan tipe 'a -> 'a

Seperti dicatat oleh ais523, tidak cukup hanya menyandikan SKI. Berikut ini adalah penyandian untuk Z menggunakan varian polimorfik untuk memanipulasi sistem tipe. Dengan ini himpunan bagian saya harus lengkap.

Z Combinator:

fun(f)->(fun(`X(x))->(x)(`X(x)))(`X(fun(`X(x))y->f(x(`X(x)))y))

dengan tipe (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b

Bahasa konkatatif berbasis tumpukan, 4 karakter

Kurang beban

():^

GolfScript

{}.~

CJam

{}_~

GS2

• backspace, tab,, @space (saya tahu GS2 banyak menggunakan unsintables, tapi ini konyol ...)

dc (disarankan oleh @seshoumara)

[]dx

Underload telah terbukti Turing-lengkap hanya dengan penggunaan ():^(terima kasih kepada warga matematika Esolang Ørjan). Buktinya terlalu panjang untuk dijelaskan di sini, tetapi jika Anda tertarik, Anda dapat membacanya di sini .

Perintah yang dimaksud adalah ()(kode tempat literal pada stack), :(duplikat elemen tumpukan atas), dan ^(evaluasi atas tumpukan). Perintah-perintah ini cukup umum dalam bahasa berbasis stack (terutama bahasa concatenative), jadi saya telah memberikan koleksi mereka di atas; bahasa-bahasa ini semuanya Turing-selesai dalam 4 karakter dengan alasan yang sama dengan Underload.

Spasi, 3 karakter

STL

Sadalah ruang, Ttab, dan Lbaris baru.

Racket (Skema), 4 karakter

(λ)

Dengan hanya menggunakan λ, kurung, dan spasi, kita dapat langsung memprogram dalam subset Kalkulus Lambda dari Skema. Kami menggunakan kembali karakter λ untuk semua pengidentifikasi dengan menggabungkannya bersama-sama untuk memberikan pengidentifikasi unik dalam jumlah besar secara sewenang-wenang.

Sebagai contoh, berikut adalah kombinasi Omega klasik, yang berulang selamanya.

((λ (λλ) (λλ λλ)) (λ (λλ) (λλ λλ)))

Python 3, 9 karakter

exc('%1+)

Lihat saya jawaban Python 2 untuk penjelasan dasar. Jawaban ini dibangun berdasarkan jawaban itu.

Alih-alih hanya menggunakan karakter yang sama dengan Python dua dengan tambahan (), kita dapat menjatuhkan karakter karena kita sekarang memiliki penggunaan tanda kurung. Program masih akan memiliki bentuk dasar

exec('%c'%stuff)

tapi kami mempersingkat panjang program dengan menggunakan +alih-alih -, lalu kami dapat menghapus ~dengan menggunakan 1alih-alih 0. Kami kemudian dapat menambahkan 1, 11, dan111 untuk mendapatkan nilai ASCII yang diperlukan.

Program ini print()menjadi yang paling singkat:

exec('%c%%c%%%%c%%%%%%%%c%%%%%%%%%%%%%%%%c%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%c%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%c'%(111+1)%(111+1+1+1)%(11+11+11+11+11+11+11+11+11+1+1+1+1+1+1)%(11+11+11+11+11+11+11+11+11+11)%(111+1+1+1+1+1)%'('%')')

Cobalah online

Anda mungkin berpikir untuk diri sendiri, bagaimana cara membuat byte NUL tanpa 0? Jangan takut, belalang muda! karena kita memiliki kemampuan untuk menggunakan %matematika juga, menciptakan nol dengan 1%1.

PHP 7, 6 karakter

'().;^

Idenya adalah bahwa dimungkinkan untuk mengeksekusi kode arbitrer menggunakan konstruksi berikut:

('create_function')('','<code>')();

eval tidak akan berfungsi di sini, karena ini merupakan konstruksi bahasa dan tidak dapat dipanggil menggunakan fungsi variabel.

create_function dan kode dapat ditulis sebagai gabungan XOR bitwise dari karakter yang tersedia:

(<char1_1>^<char1_2>^...).(<char2_1>^<char2_2>^...)...

Menggunakan ().;^untuk <charX_Y>, kita bisa dapatkan

()./:;<=JKLMXY^_bcdepqvw

dan beberapa karakter yang tidak patut dicetak. Itu tidak cukup, tetapi sekarang kita dapat memanggil 'eXp'()dan mendapatkan beberapa karakter numerik juga:

''.'eXp'('eXp'('')) -> 1
''.'eXp'('eXp'('eXp'(''))) -> 2.718281828459
''.'eXp'('eXp'('eXp'('eXp'('eXp'(''))))) -> 3814279.1047602

Ini memberi kita 1, 2dan 3(karakter lain akan diabaikan oleh XOR, jika string lainnya panjangnya satu karakter). Dari ().;^123sekarang kita dapat menghasilkan semua charset ASCII.

Cobalah online

Pyke, 5 karakter

0h.CE

Ini mampu menghasilkan angka yang sangat besar, mengubahnya menjadi string dan kemudian mengevaluasinya sebagai kode Pyke.

Penjelasan kode:

0- Tambahkan 0 ke tumpukan. Ini diperlukan untuk memulai nomor

h- Menambah nomor sebelumnya. Dengan mengulangi jumlah ini sembarang kali, Anda dapat membuat angka yang jauh lebih besar. Pyke mendukung bignum seperti yang tertulis dalam Python, yang menggunakannya sebagai default.

.C- Ubah angka menjadi string menggunakan algoritma berikut: ( Tautan Github )

def to_string(num):
    string = ""
    while num > 256:
        num, new = divmod(num, 256)
        string = chr(new) + string
    string = chr(num) + string
    return string

Pada titik ini, kita dapat membuat jumlah string dan bilangan alami sewenang-wenang di Pyke dengan nilai arbitrer. Angka dapat dibuat dalam bentuk yang sesuai dengan regex 0(h)*dan string dapat dibuat dengan 0(h)*.C. Mereka dapat terjalin satu sama lain untuk menciptakan campuran string dan integer yang berubah-ubah.

E- Mengevaluasi string sebagai kode Pyke. Ini menggunakan lingkungan yang sama dengan kode Pyke yang sudah berjalan sehingga akan berbagi hal-hal seperti input.

Mencoba bukti bahwa Pyke Turing Lengkap.

Salah satu cara paling sederhana untuk menunjukkan bahasa adalah menyelesaikan turing adalah dengan mengimplementasikan Brainf * ck di dalamnya. Ini mungkin jauh lebih sulit di Pyke daripada banyak bahasa lain karena itu daftar dan operasi kamus cukup banyak tidak ada karena kurangnya membutuhkan mereka di area Pyke dirancang untuk dijalankan: kode-golf .

Pertama-tama kita membuat interpreter untuk brainf * ck dan menyandikannya menggunakan algoritma kami di atas untuk membuat angka dan kemudian menyatakan angka itu dengan 0dan h. Kami kemudian membuat string yang berisi kode untuk dijalankan dengan cara yang persis sama. Jika kita berhenti di situ, kita akan memiliki tumpukan sebagai

string containing brainf*ck code
string containing brainf*ck interpreter

Ini berarti kode harus dalam bentuk yang berlawanan karena tumpukan Pyke adalah yang pertama keluar terakhir.

Sekarang untuk bagian yang menyenangkan: penerjemah brainf * ck dengan 216 byte kekalahan!

Q~B"><ht.,".:=B;Z]1=L;W~Bo@D=c"ht"{I~c~LZ@EZ]1~LR3:=L)~c\,qIz.oZ]1~LR3:=L)~c\[email protected])~c"<>"{I~c"<>""th".:ZE=ZZ1_qI0=Z~L0"":0]10:=L)Z~LlqI~L~Ll"":1_]10:=L))~c\[qI~LZ@0qI\]~B~o>@~o+h=o))~c\]qI~o\[~B~o<_@-t=o)~o~BlN

Coba di sini!

Jika Anda ingin mencoba kode dalam bentuk setengah jadi tetapi dapat diedit, coba di sini!

Untuk mengonversi dari string menjadi angka, Anda dapat menggunakan kode Python berikut:

def conv(string, t=0):
    t *= 256
    t += ord(string[0])
    if len(string) != 1:
        return conv(string[1:], t)
    return t

Solusi terakhir (hampir) dapat dicoba di sini!

Penjelasan dari Brainf * ck interpreter

Pertama mari kita pisahkan program menjadi beberapa bagian:

• Inisialisasi:

​

Q~B"><ht.,".:=B;Z]1=L; - The initialisation part
Q~B"><ht.,".:          - input.replace("><+-.,[]", "><ht.,")
                       - replace the characters in brainf*ck with some modified ones. 
                       - this means we can `eval` the add and subtract bits easily.
             =B;       - set `B` to this.
                       - The `B` variable contains the instructions
                Z]1=L; - set `L` to [0]
                       - `L` contains the stack, initialised with 0

• Loop utama:

​​ ​ ​

W~Bo@D=c !code! ~o~BlN - The main loop
W                      - do
 ~Bo@D=c               -  c=B[o++]
                       -  the c variable is used to store the current character.
                ~o~BlN - while
                ~o     -   o 
                     N -  ^ != V 
                  ~Bl  -   len(B)
                       -  this stops the program running once it's finished.

• Instruksi
  • Kenaikan / Decrement:+-

​​ ​ ​

"ht"{I~c~LZ@EZ]1~LR3:=L) - The bit that does incrementing and decrementing
"ht"{I                 ) - if c in "ht"
        ~LZ@             -  L[Z]
                         -  `Z` contains the current stack pointer
      ~c    E            -  eval current character with ^ as an argument
                         -  returns the contents of `Z` either incremented or decremented
             Z]1~LR3:=L  - L[Z] = ^

• Masukan ,::

​​ ​ ​

~c\,qIz.oZ]1~LR3:=L) - The code for output 
~c\,qI             ) -  if character == ",":
      z.o            -    ord(input)
         Z]1~LR3:=L  -   L[Z] = ^

• Output .::

​​ ​ ​

~c\[email protected]) - The code for input 
~c\.qI        ) - if c == ".":
      ~LZ@      -    L[Z]
          .C    -   chr(^)
            pK  -  print(^)

• Shift Kiri / Kanan <>::

​​ ​ ​

~c"<>"{I~c"<>""th".:ZE=Z - main part 
~c"<>"{I                 - if "<>" in c:
        ~c"<>""th".:     -  c.replace("<>", "th")
                    ZE=Z -  Z = eval(char, Z)

Z1_qI0=Z~L0"":0]10:=L) - lower bound check
Z1_qI                ) - if Z == -1:
     0=Z               -  Z = 0
        ~L0"":         -  L.insert("", 0)
              0]10:=L  -  L[0] = 0

Z~LlqI~L~Ll"":1_]10:=L) - upper bound check
Z~LlqI                ) - if Z == len(L):
        ~Ll"":          -  L.insert("", len(L))
      ~L      1_]10:=L  -  L[-1] = 0

• Persyaratan [::

​​ ​ ​

~c\[qI~LZ@0qI\]~B~o>@~o+h=o)) - Code for `[`
~c\[qI                      ) - if c == "[":
      ~LZ@0qI              )  -  if L[Z] == 0:
               ~B~o>          -     B[o:]
             \]     @         -    ^.find("]")
                     ~o+h=o   -   o = o + ^ + 1

- Dan ] :

​​ ​ ​

~c\]qI~o\[~B~o<_@-t=o) - Code for `]`
~c\]qI               ) - if c == "]":
          ~B~o<_       -    reversed(B[:o])
        \[      @      -   ^.find("[")
      ~o         -t=o  -  o = o - ^ -1

Ditumpuk, 5 karakter

{!n:}

Ini sangat singkat. Jika Stacked dapat menerapkan masing-masing kombinasi SKI, maka Turing Lengkap. Rekap:

• I combinator - fungsi identitas. x -> x
• K combinator - fungsi konstan. x -> y -> x
• S combinator - fungsi substitusi. (x, y, z) -> x(z)(y(z))

Saya mengkombinasikan: {!n}

Sekarang, untuk spesifik yang ditumpuk. {! ... }adalah n-lambda. Ini adalah fungsi unary yang argumennya secara implisit n. Kemudian, ekspresi terakhir dikembalikan dari fungsi. Jadi, {!n}adalah fungsi yang mengambil argumen ndan hasil n.

K combinator: {!{:n}}

Sekarang, {:...}adalah fungsi yang tidak memerlukan argumen, dan mengembalikan .... Menggabungkan ini dengan formasi n-lambda kami, kami dapatkan (menambahkan spasi kosong untuk kejelasan):

{! { : n } }
{!         }   n-lambda. arguments: (n)
   { : n }     lambda.   arguments: ()
       n       yields n.

S Combinator: {n!nn!nnn:nnn{!n}!nn!nnn{!n}!n!!}

Ok, ini terlihat sedikit lebih rumit. Jadi, lambda mengambil argumen, dipisahkan oleh karakter yang tidak dapat diidentifikasi. Dengan demikian, lambda di header sama dengan:

{n nn nnn:nnn{!n}!nn!nnn{!n}!n!!}

Ini adalah lambda yang mengambil tiga argumen, n, nn, dan nnn. Mari kita mengganti ini dengan x, y, dan zuntuk kejelasan:

{x y z:z{!n}!y!z{!n}!x!!}

Keduanya {!n}!hanyalah fungsi identitas untuk kembali menghindari spasi putih, di mana !berarti "mengeksekusi". Jadi, sekali lagi, mengurangi:

{x y z:z y!z x!!}

Dengan penjelasan:

{x y z:z y!z x!!}
{x y z:         }  three arguments
       z y!        apply `y` to `z` -- `y(z)`
           z x!    apply `x` to `z` -- `x(z)`
               !   apply `x(z)` to `y(z)` -- `x(z)(y(z))`

Dan karena itu, ini adalah kombinator S.