Sebuah kalimat nomor teori (untuk tujuan kita) adalah urutan simbol-simbol berikut:
0
dan'
(penerus) - penerus artinya+1
, jadi0'''' = 0 + 1 + 1 + 1 + 1 = 4
+
(penjumlahan) dan*
(penggandaan)=
(sama dengan)(
dan)
(tanda kurung)- operator logis
nand
(a nand b
adalahnot (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 x
adalah 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 n
dalam 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 yes
jika itu benar dan no
jika tidak.
Anda tidak perlu mendukung satu variabel menjadi subjek forall
dua 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 kode-golf , jadi cobalah membuat program Anda sesingkat mungkin!
sumber
v number
?var number
, atau bahkan hanya1 + number
(demikian1
jugav0
,2
akanv1
, dll.)'v number
alih-alihv number'
jika kita memilih opsi awalan-sintaks?Jawaban:
Python 2 ,
252236 byteCobalah online!
Mengambil input sebagai sintaks awalan bersarang, dengan
f
bukannyaforall
dann
bukannyanand
:sumber
print(eval(g(*input())))
.APL (Dyalog Unicode) , 129 byte SBCS
Cobalah online!
Mengambil pohon sintaks awalan seperti pada jawaban python TFeld , tetapi menggunakan pengkodean bilangan bulat. Pengkodean adalah
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
Cobalah online!
sumber