Menentukan apakah mesin Turing berhenti dikenal tidak dapat diputuskan, tetapi itu tidak selalu benar untuk mesin yang lebih sederhana.
Sebuah mesin Foo adalah mesin dengan pita yang terbatas, di mana setiap sel dalam rekaman memiliki integer atau simbol berhenti h
, misalnya
2 h 1 -1
Penunjuk instruksi dimulai dengan menunjuk ke sel pertama:
2 h 1 -1
^
Pada setiap langkah, penunjuk instruksi bergerak maju dengan angka yang ditunjukkannya, lalu meniadakan angka itu. Jadi, setelah satu langkah, itu akan bergerak maju 2
sel, dan mengubah 2
menjadi -2
:
-2 h 1 -1
^
Mesin Foo terus melakukan ini sampai penunjuk instruksi menunjuk ke simbol berhenti ( h
). Jadi, inilah eksekusi penuh dari program ini:
2 h 1 -1
^
-2 h 1 -1
^
-2 h -1 -1
^
-2 h -1 1
^
-2 h 1 1
^
Pita itu juga melingkar, jadi jika penunjuk instruksi bergerak dari satu sisi pita, ia pergi ke sisi lain, misalnya:
3 h 1 3
^
-3 h 1 3
^
-3 h 1 -3
^
-3 h -1 -3
^
-3 h -1 3
^
3 h -1 3
^
Satu hal yang menarik tentang mesin Foo ini adalah beberapa tidak berhenti, misalnya:
1 2 h 2
^
-1 2 h 2
^
-1 -2 h 2
^
-1 -2 h -2
^
-1 2 h -2
^
-1 2 h 2
^
Program ini akan terus berulang dalam empat negara terakhir selamanya.
Jadi, tulislah sebuah program yang menentukan apakah mesin Foo berhenti atau tidak! Anda dapat menggunakan format input (wajar) apa pun yang Anda suka untuk mesin Foo, dan Anda dapat memilih untuk menggunakan 0
sebagai simbol berhenti. Anda dapat menggunakan dua output berbeda untuk case di mana ia berhenti dan case di mana tidak. Program Anda harus, tentu saja, menghasilkan jawaban dalam jumlah waktu yang terbatas untuk semua input yang valid.
Ini adalah kode-golf , jadi cobalah membuat program Anda sesingkat mungkin!
Uji kasus
2 h 1 -1
Halts
3 h 1 3
Halts
h
Halts
1 1 1 1 h
Halts
2 1 3 2 1 2 h
Halts
3 2 1 1 4 h
Halts
1 -1 -2 -3 -4 -5 -6 -7 -8 -9 -10 -11 -12 -13 -14 -15 -16 -17 -18 h -20 -21 -22 -23 -24 -25 -26 -27 -28 -29 -30 -31 -32 -33 -34 -35 -36
Halts
2 h
Does not halt
1 2 h 2
Does not halt
8 1 2 3 3 4 8 4 3 2 h
Does not halt
1 2 4 3 h 2 4 5 3
Does not halt
3 1 h 3 1 1
Does not halt
1 2 h 42
Does not halt
sumber
1 2 h 42
(tidak berhenti)3 2 1 1 4 h
. Yang ini berhenti tetapi membutuhkan lebih banyak iterasi daripada dua kali jumlah elemen.1 -1 -2 -3 -4 -5 -6 -7 -8 -9 -10 -11 -12 -13 -14 -15 -16 -17 -18 h -20 -21 -22 -23 -24 -25 -26 -27 -28 -29 -30 -31 -32 -33 -34 -35 -36
Case uji ekstra panjang yang disarankan :, yang berhenti setelah langkah 786430.Jawaban:
C # (Visual C # Interactive Compiler) , 71 byte
Cobalah online!
Saya tidak tahu apakah yang berikut ini valid, karena memerlukan delegasi khusus dengan tanda tangan
unsafe delegate System.Action<int> D(int* a);
dan harus dibungkus denganunsafe
blok untuk digunakan, tetapi ini dia:C # (.NET Core) , 64 byte
Cobalah online!
Fungsi ini mengambil int * dan mengembalikan Aksi; dengan kata lain, itu adalah fungsi kari. Satu-satunya alasan saya menggunakan pointer adalah karena codegolf.meta.stackexchange.com/a/13262/84206, yang memungkinkan saya untuk menyimpan byte dengan sudah memiliki variabel yang sudah ditentukan dengan panjang array.
Disimpan 9 byte berkat @someone
sumber
1<<f
dengan2*f
untuk menyimpan byte.Python 3 ,
6389 byteCobalah online!
Juga berfungsi untuk Python 2; byte dapat disimpan dalam Python 2 dengan mengganti kembali dengan cetak dan memiliki fungsi cetak ke stdout bukannya kembali. R berbelok
True
untuk berhenti danFalse
untuk tidak berhenti.Terima kasih kepada @Neil dan @Arnauld karena memperhatikan bahwa saya perlu memeriksa lebih lama untuk berhenti. Terima kasih kepada @Jitse karena menunjukkan masalah dengan
[2,0]
. Terima kasih kepada @mypetlion karena mencatat bahwa nilai absolut rekaman dapat melebihi panjang rekaman.sumber
x+x
sudah cukup?[ 3, 2, 1, 1, 4, 0 ]
, yang berhenti di lebih dari 12 iterasi.len(x)*x
[8,7,6,5,7,4,0,3,6]
2**len(x)
masih sedikit kekurangan maksimum? Saya menghitung jumlah negara sebagain*(2**n)
(dengann=len(x)-1
).Jelly ,
1511 byteCobalah online!
Tautan monadik yang mengambil input sebagai daftar bilangan bulat menggunakan 0 berarti berhenti. Mengembalikan 0 untuk menghentikan input dan 1 untuk input yang tidak berhenti.
Hindari masalah perlunya menghitung beberapa iterasi karena penggunaannya
ÐL
akan berulang sampai tidak ada hasil baru yang terlihat.Terima kasih kepada @JonathanAllan karena telah menghemat satu byte!
Penjelasan
sumber
N1¦ṙ⁸ḢƊÐLḢẸ
Python 3 , 91 byte
Cobalah online!
-40 byte berkat JoKing dan Jitse
sumber
while
kondisinya.Perl 6 ,
46 4336 byteCobalah online!
Merupakan penghentian
0
dan mengembalikan true jika mesin berhenti. Ini mengulangi waktu logika2**(length n)
, di mana jika pointer berakhir pada sel berhenti, itu tetap di sana, jika tidak maka akan berada di sel non-berhenti.Ini berfungsi karena hanyaOke ya, ada status dari itu, tetapi karena transisi yang mungkin terbatas antara pointer (dan karena itu menyatakan) akan ada kurang dari 2 ** $ _ menyatakan ... Saya pikir2**n
ada status yang memungkinkan (mengabaikan sel berhenti) untuk mesin Foo berada, karena setiap sel non-berhenti hanya memiliki dua negara.Penjelasan
sumber
05AB1E ,
1413 byteCobalah online!
Mengambil input sebagai daftar bilangan bulat dengan 0 sebagai instruksi penghentian. Mengembalikan 1 untuk berhenti dan 0 untuk tidak berhenti.
Terima kasih kepada @KevinCruijssen karena telah menghemat 2 byte!
sumber
ć
! Saya sedang menunggu penjelasan dengan harapan bisa golf jawaban saya, tetapi Anda mengalahkan saya untuk itu, haha. ; p -1 byte dengan melakukan golf yang sama dengan jawaban saya:g·F
to«v
( Coba online. )©®
alih-alihDŠs
:«vć©(š®._}®_
( Coba online. )«v
kegoF
.Java 8,
787973 bytePort C # .NET jawaban langsung dari @EmbodimentOfIgnorance , jadi pastikan Anda menambahkannya!
Terima kasih kepada @Arnauld untuk menemukan dua bug (yang juga berlaku untuk beberapa jawaban lain).
Menghasilkan
java.lang.ArithmeticException: / by zero
kesalahan saat itu bisa berhenti, atau tidak ada kesalahan jika tidak.Cobalah online.
Penjelasan:
sumber
int*
(dari codegolf.meta.stackexchange.com/a/13262/84206 )Haskell , 79 byte
Cobalah online!
Pengembalian
True
untuk mesin penghenti, danFalse
sebaliknya. Input dalam bentuk daftar, dengan0
mewakili keadaan terputus-putus.Diasumsikan versi GHC lebih besar dari 8,4 (dirilis Februari 2018).
sumber
JavaScript (Node.js) ,
7167 bytePada dasarnya sama dengan jawaban C # .NET .EmbodimentOfIgnorance
Simpan 4 byte berkat @Arnaud
Cobalah online!
JavaScript (Node.js) , 61 byte
Versi ini digunakan
undefined
sebagai simbol penghentian dan melemparTypeError: Cannot read property 'f' of undefined
ketika mesin berhenti dan berhenti dengan tenang ketika mesin tidak berhenti.Cobalah online!
sumber
Scala , 156 byte
IMO masih golf, tapi saya baik-baik saja dengan itu untuk saat ini. Pengembalian
0
untuk yang tidak berhentiFoo
dan1
untuk berhentiFoo
. Mengambil inputa
sebagaiArray[Int]
, jadih
diambil sebagai0
.Cukup lama untuk dijalankan (sekitar 4 detik untuk semua kasus uji) karena beberapa pencarian array penuh yang saya lakukan, ditambah
.deep
yang membuat salinan ... Tetapi Anda masih dapat mencobanya secara online.sumber
Perl 5
-ap
, 88 byteCobalah online!
sumber
Attache , 40 byte
Cobalah online!
Penjelasan
Ini melakukan iterasi tunggal dari mesin Foo; itu meniadakan anggota pertama, kemudian memutar array dengan elemen pertama (asli, tidak dinegasikan) dari array.
Periodic
akan menerapkan fungsi ini sampai hasil duplikat diakumulasikan. Sebuah mesin baik berhenti, atau masuk ke loop tak terbatas sepele. Jika berhenti, elemen pertama akan menjadi 0. Jika tidak, itu akan menjadi nol.&N
adalah cara golf untuk mendapatkan elemen pertama dari array numerik. Kemudian,Not
kembalikantrue
untuk 0 (mesin penghenti) danfalse
untuk yang lainnya (mesin non penghenti).sumber
Arang , 28 byte
Cobalah online! Tautan adalah untuk mengucapkan versi kode. Keluaran menggunakan keluaran Boolean default dari Charcoal, yang mana
-
benar dan tidak ada yang salah. Penjelasan:Inisialisasi penunjuk instruksi.
Loop sebanyak yang ada secara teoritis mungkin.
Negasikan nilai pada penunjuk instruksi.
Kurangi nilai baru dari penunjuk instruksi. Akses array Charcoal bersifat siklik sehingga ini secara otomatis mengemulasi pita bundar Foo.
Pada akhir loop, output apakah program terhenti.
sumber
Stax , 11 byte
Jalankan dan debug itu
Dibutuhkan input dalam bentuk array integer, dengan
0
mewakili penghentian.Ini output
1
untuk berhenti dan0
untuk mesin non-berhenti.sumber
Pyth , 12 byte
Suite uji!
Menggunakan pendekatan lurus ke depan. Perulangan sampai kita melihat daftar dua kali dalam keadaan yang identik. Untuk program yang berhenti, daftar akhirnya akan memiliki yang memimpin
0
karena di situlah rekursi berhenti. Untuk program yang tidak berhenti, daftar tidak akan dimulai dengan0
, tetapi berada dalam keadaan di mana prosesnya akan berkala dan karena itu mesin Foo tidak akan berhenti.sumber