Komputasi tabel bever dan algoritma yang tidak diketahui berakhir di ZFC

12

The Laver tabel memberikan contoh program yang belum ditampilkan untuk mengakhiri dalam sistem aksiomatik standar matematika ZFC tetapi yang berakhir pada saat kita menganggap aksioma kardinal yang sangat besar.

pengantar

Tabel Laver klasik adalah aljabar terbatas yang unik dengan himpunan yang mendasari dan operasi yang memenuhi identitas dan di mana untuk dan di mana .An{1,...,2n}*x * (y * z)=(x * y) * (x * z)x*1=x+1x<2n2n*1=1

Informasi lebih lanjut tentang tabel Laver klasik dapat ditemukan dalam buku Braids and Self-Distributivity oleh Patrick Dehornoy.

Tantangan

Apa kode terpendek (dalam byte) yang menghitung 1*32dalam tabel Laver klasik dan berakhir tepat ketika ia menemukan sebuah ndengan ? Dengan kata lain, program berakhir jika dan hanya jika ia menemukan dengan tetapi jika tidak berjalan selamanya.1*32<2nn1*32<2n

Motivasi

Sebuah peringkat-ke-rank cardinal (juga disebut I3-kardinal) adalah sangat besar tingkat infinity dan jika kita menganggap keberadaan seorang kardinal peringkat-ke-rank, maka seseorang dapat membuktikan lebih teorema daripada jika salah satu tidak mengasumsikan keberadaan kardinal pangkat-ke-pangkat. Jika ada kardinal peringkat ke peringkat, maka ada beberapa tabel Laver klasik di mana . Namun, tidak ada bukti yang diketahui di ZFC. Selain itu, diketahui bahwa paling sedikit di mana lebih besar dari (yang merupakan jumlah yang sangat besar karena fungsi Ackermann adalah fungsi yang tumbuh cepat). Oleh karena itu, program semacam itu akan bertahan untuk waktu yang sangat lama.An1*32<2n1*32<2nn1*32<2nAck(9,Ack(8,Ack(8,254)))Ack

Saya ingin melihat seberapa pendek suatu program dapat ditulis sehingga kita tidak tahu apakah program berakhir menggunakan sistem aksiomatik standar ZFC tetapi di mana kita tahu bahwa program akhirnya berakhir dalam sistem aksiomatik yang jauh lebih kuat, yaitu ZFC + I3. Pertanyaan ini diinspirasi oleh pos Scott Aaronson baru-baru ini di mana Aaronson dan Adam Yedidia telah membangun mesin Turing dengan di bawah 8000 negara sehingga ZFC tidak dapat membuktikan bahwa mesin Turing tidak berakhir tetapi diketahui tidak akan berhenti ketika seseorang mengasumsikan hipotesis kardinal besar.

Bagaimana tabel Laver klasik dihitung

Ketika komputasi tabel Laver biasanya mudah untuk menggunakan fakta bahwa dalam aljabar yang , kita memiliki semua di .An2n * x=xxAn

Kode berikut menghitung tabel Laver klasik An

# table (n, x, y) mengembalikan x * y dalam A n
tabel: = fungsi (n, x, y)
jika x = 2 ^ n maka kembalikan y;
elif y = 1 lalu kembalikan x + 1;
selain itu kembali tabel (n, tabel (n, x, y-1), x + 1); fi; akhir;

Misalnya, input table(4,1,2)akan kembali 12.

Kode untuk table(n,x,y)agak tidak efisien dan hanya dapat dihitung dalam tabel Laver dalam jumlah waktu yang wajar. Untungnya, ada banyak algoritma yang lebih cepat untuk menghitung tabel Laver klasik daripada yang diberikan di atas.A4

Joseph Van Name
sumber
2
Selamat datang di PPCG! Pos yang bagus!
NoOneIsHere
1
Menurut Wikipedia, Ack (9, Ack (8, Ack (8.254)))) adalah batas yang lebih rendah pada n di mana periode melebihi 16. Untuk itu, kita dapat memeriksa 1 * 16 daripada 1 * 32. Saya akan mengubah program saya sesuai.
John Tromp
1
Saya sudah mulai menulis mesin Turing untuk melakukan ini, dan saya pikir saya telah menemukan kesalahan faktor-dua. Bukankah Dougherty membuktikan bahwa itu Ack(9,Ack(8,Ack(8,254)))adalah batas bawah untuk tabel pertama di mana baris pertama memiliki periode 32, yaitu di mana 1*16 < 2^n?
Peter Taylor
1
Jika Anda memiliki mesin 2-simbol 20-negara untuk Ackermann maka tolong beri saya tautan, karena saya mungkin dapat mencuri beberapa ide darinya. Saya memiliki 44 negara untuk menghitung table(n,x,y), dan saya pikir akan membutuhkan antara 25 dan 30 negara untuk mengatur konstanta dan lingkaran luar. Satu-satunya perwakilan TM langsung yang dapat saya temukan di esolangs.org adalah esolangs.org/wiki/ScripTur dan tidak terlalu golf.
Peter Taylor
1
cheddarmonk.org/papers/laver.pdf adalah sebanyak yang saya harapkan akan selesai minggu ini, karena saya akan bepergian.
Peter Taylor

Jawaban:

4

Binary Lambda Calculus, 215 bit (27 bytes)

\io. let
  zero = \f\x. x;
  one = \x. x;
  two = \f\x. f (f x);
  sixteen = (\x. x x x) two;
  pred = \n\f\x. n (\g\h. h (g f)) (\h. x) (\x. x);
  laver = \mx.
    let laver = \b\a. a (\_. mx (b (laver (pred a))) zero) b
    in laver;
  sweet = sixteen;
  dblp1 = \n\f\x. n f (n f (f x)); -- map n to 2*n+1
  go2 = \mx. laver mx sweet mx (\_. mx) (go2 (dblp1 mx));
in go2 one

kompilasi ke (menggunakan perangkat lunak di https://github.com/tromp/AIT )

000101000110100000010101010100011010000000010110000101111110011110010111
110111100000010101111100000011001110111100011000100000101100100010110101
00000011100111010100011001011101100000010111101100101111011001110100010

Solusi ini sebagian besar disebabkan oleh https://github.com/int-e

John Tromp
sumber
2
Saya tidak yakin bagaimana Anda mendapatkan skor Anda, tetapi dengan pengiriman standar harus dinilai sesuai dengan jumlah byte dalam kode. Saya menghitung 375 byte untuk pengiriman ini. Anda juga harus memasukkan nama bahasa dan secara opsional tautan ke juru bahasa.
Alex A.
Anda mungkin harus memasukkan kode persis panjang 234 bit dalam posting Anda.
CalculatorFeline
2
Pengkodean dapat ditemukan di Wikipedia . Ada juga tautan ke juru bahasa ini (tidak diuji). Ini harus diperiksa, dan penyandian biner juga harus dalam pos.
PurkkaKoodari
1
Untuk bahasa yang dikompilasi, kami mencetak kode yang ditulis oleh pengguna - bukan jumlah byte dalam biner yang dihasilkan.
Alex A.
5
@AlexA. Itu tidak perlu ... segala bentuk kode yang dapat dipahami oleh kompiler atau juru bahasa baik-baik saja.
feersum
4

CJam ( 36 32 byte)

1{2*31TW$,(+a{0X$j@(@jj}2j)W$=}g

Dalam praktiknya, kesalahan ini keluar cukup cepat karena melebihi tumpukan panggilan, tetapi pada mesin tanpa batas teoretis itu benar, dan saya mengerti bahwa menjadi asumsi pertanyaan ini.

Kode untuk table(n,x,y)ini agak tidak efisien dan hanya dapat dihitung dalam tabel Laver A 4 dalam jumlah waktu yang wajar.

sebenarnya tidak benar jika kita men-cache nilai komputasi untuk menghindari penghitungan ulang. Itulah pendekatan yang saya ambil, menggunakan joperator (memoisasi) . Ini menguji A 6 dalam milidetik dan meluap pengujian tumpukan A 7 - dan saya benar-benar deoptimised table untuk kepentingan golf.

Pembedahan

Jika kita menganggap itu ndipahami dari konteksnya, alih-alih

f(x,y) =
    x==2^n ? y :
    y==1 ? x+1 :
    f(f(x,y-1),x+1)

kita dapat menghapus kasus khusus pertama, memberi

f(x,y) =
    y==1 ? x+1 :
    f(f(x,y-1),x+1)

dan masih bekerja karena

f(2^n, 1) = 2^n + 1 = 1

dan untuk yang lain y,

f(2^n, y) = f(f(2^n, y-1), 1) = f(2^n, y-1) + 1

jadi dengan induksi kita dapatkan f(2^n, y) = y.

Untuk CJam ternyata lebih mudah untuk membalik urutan parameter. Dan alih-alih menggunakan rentang 1 .. 2^nsaya menggunakan rentang 0 .. 2^n - 1dengan mengurangi setiap nilai, jadi fungsi rekursif yang saya implementasikan adalah

g(y,x) =
    y==0 ? x+1
         : g(x+1, g(y-1, x))

1           e# Initial value of 2^n
{           e# do-while loop
  2*        e#   Double 2^n (i.e. increment n)
  31T       e#   table(n,1,32) is g(31,0) so push 31 0
  W$,(+a    e#   Set up a lookup table for g(0,x) = x+1 % 2^n
  {         e#   Memoisation function body: stack is 2^n ... y x
    0X$j    e#     Compute g(0,x) = x+1 % 2^n
            e#     Stack is 2^n ... y x (x+1%2^n)
    @(      e#     Bring y to top, decrement (guaranteed not to underflow)
            e#     Stack is 2^n ... x (x+1%2^n) (y-1%2^n)
    @jj     e#     Rotate and apply memoised function twice: g(x+1,g(y-1,x))
  }
  2j        e#   Memoise two-parameter function
            e#   Stack: 2^n g(31,0)
  )W$=      e#   Test whether g(31,0)+1 is 2^n
}g          e# Loop while true
Peter Taylor
sumber
1

Pyth, 33 byte

.N?qT^2NY?tY:N:NTtYhThT<:T1 32^2T

Cobalah online! (Jelas bagian pengujian tidak termasuk di sini.)

Biarawati Bocor
sumber
Lingkaran apa? Juga, apa artinya fidalam kode?
Leaky Nun