Penerjemah untuk teori bilangan, modulo n

12

Sebuah kalimat nomor teori (untuk tujuan kita) adalah urutan simbol-simbol berikut:

  • 0dan '(penerus) - penerus artinya +1, jadi0'''' = 0 + 1 + 1 + 1 + 1 = 4
  • +(penjumlahan) dan *(penggandaan)
  • = (sama dengan)
  • (dan )(tanda kurung)
  • operator logis nand( a nand badalah not (a and b))
  • forall (quantifier universal)
  • v0, v1, v2, Dll (variabel)

    Ini adalah contoh kalimat:

forall v1 (forall v2 (forall v3 (not (v1*v1*v1 + v2*v2*v2 = v3*v3*v3))))

Ini not xadalah singkatan untuk x nand x- kalimat yang sebenarnya akan digunakan (v1*v1*v1 + v2*v2*v2 = v3*v3*v3) nand (v1*v1*v1 + v2*v2*v2 = v3*v3*v3), karena x nand x = not (x and x) = not x.

Ini menyatakan bahwa untuk setiap kombinasi dari tiga bilangan v1, v2, dan v3, itu tidak terjadi bahwa v1 3 + v2 3 = v3 3 (yang akan menjadi kenyataan karena Fermat Teorema Terakhir, kecuali untuk fakta bahwa itu akan mendapatkan 0 ^ 3 + 0 ^ 3 = 0 ^ 3).

Sayangnya, sebagaimana dibuktikan oleh Gödel, tidak mungkin untuk menentukan apakah kalimat dalam teori bilangan benar atau tidak.

Hal ini dimungkinkan, namun, jika kita membatasi set angka alami untuk set terbatas.

Jadi, tantangan ini adalah untuk menentukan apakah kalimat teori bilangan benar atau tidak, ketika diambil modulo n , untuk beberapa bilangan bulat positif n. Misalnya kalimatnya

forall v0 (v0 * v0 * v0 = v0)

(pernyataan bahwa untuk semua angka x, x 3 = x)

Ini tidak berlaku untuk aritmatika biasa (misalnya 2 3 = 8 ≠ 2), tetapi adalah benar ketika diambil modulo 3:

0 * 0 * 0 ≡ 0 (mod 3)
1 * 1 * 1 ≡ 1 (mod 3)
2 * 2 * 2 ≡ 8 ≡ 2 (mod 3)

Format input dan output

Masukan adalah kalimat dan bilangan bulat positif ndalam format "wajar" apa pun. Berikut adalah beberapa contoh format yang masuk akal untuk kalimat forall v0 (v0 * v0 * v0 = v0)dalam teori bilangan modulo 3:

("forall v0 (v0 * v0 * v0 = v0)", 3)
"3:forall v0 (((v0 * v0) * v0) = v0)"
"(forall v0)(((v0 * v0) * v0) = v0) mod 3" 
[3, "forall", "v0", "(", "(", "(", "v0", "*", "v0", ")", "*", "v0", ")", "=", "v0", ")"]
(3, [8, 9, 5, 5, 5, 9, 3, 9, 6, 3, 9, 6, 4, 9, 6]) (the sentence above, but with each symbol replaced with a unique number)
"f v0 = * * v0 v0 v0 v0"
[3, ["forall", "v0", ["=", ["*", "v0", ["*", "v0", "v0"]], "v0"]]]
"3.v0((v0 * (v0 * v0)) = v0)"

Input dapat dari stdin, argumen baris perintah, file, dll.

Program dapat memiliki dua keluaran berbeda untuk menentukan apakah kalimat itu benar atau tidak, misalnya dapat menghasilkan yesjika itu benar dan nojika tidak.

Anda tidak perlu mendukung satu variabel menjadi subjek foralldua kali, misalnya (forall v0 (v0 = 0)) nand (forall v0 (v0 = 0)). Anda dapat mengasumsikan bahwa input Anda memiliki sintaks yang valid.

Uji kasus

forall v0 (v0 * v0 * v0 = v0) mod 3
true

forall v0 (v0 * v0 * v0 = v0) mod 4
false (2 * 2 * 2 = 8 ≡ 0 mod 4)

forall v0 (v0 = 0) mod 1
true (all numbers are 0 modulo 1)

0 = 0 mod 8
true

0''' = 0 mod 3
true

0''' = 0 mod 4
false

forall v0 (v0' = v0') mod 1428374
true

forall v0 (v0 = 0) nand forall v1 (v1 = 0) mod 2
true (this is False nand False, which is true)

forall v0 ((v0 = 0 nand v0 = 0) nand ((forall v1 (v0 * v1 = 0' nand v0 * v1 = 0') nand forall v2 (v0 * v2 = 0' nand v0 * v2 = 0')) nand (forall v3 (v0 * v3 = 0' nand v0 * v3 = 0') nand forall v4 (v0 * v4 = 0' nand v0 * v4 = 0')))) mod 7
true
(equivalent to "forall v0 (v0 =/= 0 implies exists v1 (v0 * v1 = 0)), which states that every number has a multiplicative inverse modulo n, which is only true if n is 1 or prime)

forall v0 ((v0 = 0 nand v0 = 0) nand ((forall v1 (v0 * v1 = 0' nand v0 * v1 = 0') nand forall v2 (v0 * v2 = 0' nand v0 * v2 = 0')) nand (forall v3 (v0 * v3 = 0' nand v0 * v3 = 0') nand forall v4 (v0 * v4 = 0' nand v0 * v4 = 0')))) mod 4
false

Ini , jadi cobalah membuat program Anda sesingkat mungkin!

Leo Tenenbaum
sumber
1
Apakah nama variabel selalu dalam format v number?
Jo King
1
@JoKing Mereka bisa jika Anda ingin mereka menjadi- Anda dapat menggunakan var number, atau bahkan hanya 1 + number(demikian 1juga v0, 2akan v1, dll.)
Leo Tenenbaum
1
@ JOOKING Anda harus mengizinkan (secara teoritis) jumlah variabel yang tak terbatas. Tidak apa-apa jika jumlah maksimum variabel dibatasi oleh ukuran maksimum bilangan bulat, tetapi Anda seharusnya tidak memiliki batas rendah. Anda dapat memilih salah satu format input lain jika ini merupakan masalah bagi Anda.
Leo Tenenbaum
1
@UnrelatedString Tentu, asalkan mereka bisa lama sewenang-wenang.
Leo Tenenbaum
1
Bisakah kita menggunakan 'v numberalih-alih v number'jika kita memilih opsi awalan-sintaks?
Tn. Xcoder

Jawaban:

3

Python 2 , 252 236 byte

def g(n,s):
 if str(s)==s:return s.replace("'","+1")
 o,l,r=map(g,[n]*3,s);return['all((%s)for %s in range(%d))'%(r,l,n),'not((%s)*(%s))'%(l,r),'(%s)%%%d==(%s)%%%d'%(l,n,r,n),'(%s)%s(%s)'%(l,o,r)]['fn=+'.find(o)]
print eval(g(*input()))

Cobalah online!

Mengambil input sebagai sintaks awalan bersarang, dengan fbukannya foralldan nbukannya nand:

[3, ["f", "v0", ["=", ["*", "v0", ["*", "v0", "v0"]], "v0"]]]
TFeld
sumber
Saat ini sedang mengeluarkan kode Python, tetapi seharusnya memiliki dua keluaran yang berbeda karena jika kalimat itu benar atau salah. Anda bisa menggunakannya print(eval(g(*input()))).
Leo Tenenbaum
@LeoTenenbaum Ya, saya memilikinya pada versi pertama, tetapi lupa untuk menambahkannya kembali setelah bermain golf
TFeld
1

APL (Dyalog Unicode) , 129 byte SBCS

{x y z3↑⍵⋄7x:y×7<x5x:∧/∇¨y{⍵≡⍺⍺:⍵⍺⋄x y z3↑⍵⋄7x:⍵⋄6x:x(⍺∇y)⋄x(⍺∇⍣(5x)⊢y)(⍺∇z)}∘z¨⍳⍺⍺⋄y←∇y6x:1+yy(⍎x'+×⍲',⊂'0=⍺⍺|-')∇z}

Cobalah online!

Mengambil pohon sintaks awalan seperti pada jawaban python TFeld , tetapi menggunakan pengkodean bilangan bulat. Pengkodean adalah

plus times nand eq forall succ zero  1 2 3 4 5 6 7

dan masing-masing variabel diberi nomor mulai dari 8. Pengkodean ini sedikit berbeda dari yang digunakan dalam versi yang tidak dikenali di bawah ini, karena saya men-tweak-nya ketika memasukkan kode.

Tugas ini hanya melibatkan dua input (AST dan modulo), tetapi menulisnya sebagai operator alih-alih fungsi menghindari menyebutkan modulo berkali-kali (karena selalu dilakukan melalui panggilan rekursif).

Tidak dikoleksi dengan komentar

 node types; anything 8 will be considered a var
plus times eq nand forall succ zero var←⍳8
 AST nodes have 1~3 length, 1st being the node type
 zero  zero, succ  succ arg, var  var | var value (respectively)

 to (from replace) AST  transform AST so that 'from' var has the value 'to' attached
replace←{
  ⍵≡⍺⍺:⍵⍺              variable found, attach the value
  x y z3↑⍵
  zerox:             zero or different variable: keep as is
  succx: x(⍺∇y)       succ: propagate to y
  forallx: x y(⍺∇z)   forall: propagate to z
  x(⍺∇y)(⍺∇z)          plus, times, eq, nand: propagate to both args
}
 (mod eval) AST  evaluate AST with the given modulo
eval←{
  x y z3↑⍵
  zerox:   0
  varx:    y                     return attached value
  forallx: ∧/∇¨y replacez¨⍳⍺⍺   check all replacements for given var
  succx:   1+∇y
  plusx:   (∇y)+∇z
  timesx:  (∇y)×∇z
  eqx:     0=⍺⍺|(∇y)-∇z          modulo equality
  nandx:   (∇y)⍲∇z               nand symbol does nand operation
}

Cobalah online!

Bubbler
sumber