Apakah mesin Foo ini berhenti?

43

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 2sel, dan mengubah 2menjadi -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 0sebagai 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 , 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
Leo Tenenbaum
sumber
5
Asal saya yakin, tentang algoritma untuk menyelesaikan ini. Saya bukan ahli algoritma jadi saya lebih suka bertanya sebelum pergi ke arah yang salah. Akankah mesin Foo yang tidak berhenti selalu kembali ke kondisi semula yang sebenarnya? Atau apakah ada mesin non-stop yang "kacau-perilaku"?
V. Courtois
5
@ V.Courtois Semua mesin Foo yang tidak berhenti akan berakhir dalam satu lingkaran status, karena hanya ada banyak kemungkinan keadaan di mana mesin Foo dapat berada (ada n tempat yang memungkinkan penunjuk instruksi bisa, dan 2 ^ n mungkin) konfigurasi pita). Setiap negara bagian memiliki satu dan hanya satu "negara bagian berikutnya". Jadi, jika mesin Foo berakhir kembali dalam keadaan sudah dalam, itu hanya akan terus berulang. Karena hanya ada banyak negara bagian yang terbatas, ia tidak dapat terus-menerus melompat-lompat di antara negara-negara bagian karena pada akhirnya akan berakhir pada keadaan yang sudah ada.
Leo Tenenbaum
3
Test case yang disarankan: 1 2 h 42(tidak berhenti)
Arnauld
6
Kasus uji yang disarankan: 3 2 1 1 4 h. Yang ini berhenti tetapi membutuhkan lebih banyak iterasi daripada dua kali jumlah elemen.
Arnauld
10
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 -36Case uji ekstra panjang yang disarankan :, yang berhenti setelah langkah 786430.
Magma

Jawaban:

11

C # (Visual C # Interactive Compiler) , 71 byte

x=>{for(int i=0,k=0,f=x.Count;i++<1<<f;k%=f)k-=(x[k]*=-1)%f-f;i/=x[k];}

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 dengan unsafeblok untuk digunakan, tetapi ini dia:

C # (.NET Core) , 64 byte

x=>f=>{for(int i=0,k=0;i++<1<<f;k%=f)k-=(x[k]*=-1)%f-f;k/=x[k];}

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

Perwujudan Ketidaktahuan
sumber
Memotong kode Anda dengan 2 byte: tio.run/…
IQuick 143
@ IQuick143 Tangkapan bagus, terima kasih
Perwujudan Ketidaktahuan
Saya tidak yakin apakah ada kasus tepi yang tidak akan berfungsi, tetapi tanpa merusak salah satu kasus uji saat ini Anda dapat mengganti 1<<fdengan 2*funtuk menyimpan byte.
Kevin Cruijssen
1
77 byte dengan sihir LINQ yang mengerikan dan perbaikan Arnauld . Saya tidak tahu bagaimana cara kerja solusi ini, jadi saya mungkin telah memecahkannya.
seseorang
1
63 byte melalui golf 1-byte yang normal dan mengubah IO menjadi error / no error. Tautan ke tautan
seseorang
7

Python 3 , 63 89 byte

def f(x):
 for i in range(2**len(x)):a=x[0];x[0]=-a;b=a%len(x);x=x[b:]+x[:b]
 return a==0

Cobalah 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 Trueuntuk berhenti dan Falseuntuk 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.

Nick Kennedy
sumber
5
OK, saya akan gigit: bagaimana Anda tahu x+xsudah cukup?
Neil
4
@ Neil Ini sebenarnya tidak cukup. Contoh tandingannya adalah [ 3, 2, 1, 1, 4, 0 ], yang berhenti di lebih dari 12 iterasi.
Arnauld
1
len(x)*x[8,7,6,5,7,4,0,3,6]92
2
Bukankah 2**len(x)masih sedikit kekurangan maksimum? Saya menghitung jumlah negara sebagai n*(2**n)(dengan n=len(x)-1).
OOBalance
1
@OOBalance Saya mengerti maksud Anda, karena setiap negara bagian dapat memiliki pointer di setiap sel ... namun, saya merasa ada batasan lain yang diterapkan oleh fakta bahwa setiap sel hanya dapat beralih ke dua sel lainnya. Sebagai catatan: tidak ada dalam tantangan mengatakan ada memiliki menjadi negara menghentikan pada input
Jo Raja
6

Jelly , 15 11 byte

N1¦ṙ⁸ḢƊÐLḢẸ

Cobalah 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 ÐLakan berulang sampai tidak ada hasil baru yang terlihat.

Terima kasih kepada @JonathanAllan karena telah menghemat satu byte!

Penjelasan

      ƊÐL   | Loop the following as a monad until the result has been seen before:
N1¦         | - Negate the first element
   ṙ⁸       | - Rotate left by each of the elements
     Ḣ      | - Take just the result of rotating by the first element
         Ḣ  | Finally take the first element
          Ẹ | And check if non-zero
Nick Kennedy
sumber
Simpan byte dengan memutar oleh semua entri dan kemudian hanya menjaga hasil pertama:N1¦ṙ⁸ḢƊÐLḢẸ
Jonathan Allan
5

Python 3 , 91 byte

def f(a):
	s={0,};i=0
	while{(*a,)}-s:s|={(*a,)};a[i]*=-1;i-=a[i];i%=len(a)
	return a[i]==0

Cobalah online!

-40 byte berkat JoKing dan Jitse

HyperNeutrino
sumber
@ Mengerjakan 109 byte dengan melakukan penugasan variabel di baris pertama.
Jitse
92 byte dengan mengubah konversi tuple menjadi ekspansi berbintang, tidak memulai dengan set kosong dan mengulangi whilekondisinya.
Jitse
@JoKing Sialan, saya tidak pernah belajar: hal. 93 byte kemudian.
Jitse
91 byte
Jitse
@JoKing terima kasih!
HyperNeutrino
5

Perl 6 , 46 43 36 byte

{$_.=rotate(.[0]*=-1)xx 2**$_;!.[0]}

Cobalah online!

Merupakan penghentian 0dan mengembalikan true jika mesin berhenti. Ini mengulangi waktu logika 2**(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 hanya 2**nada status yang memungkinkan (mengabaikan sel berhenti) untuk mesin Foo berada, karena setiap sel non-berhenti hanya memiliki dua negara.Oke ya, ada status dari itu, tetapi karena transisi yang mungkin terbatas antara pointer (dan karena itu menyatakan) akan ada kurang dari 2 ** $ _ menyatakan ... Saya pikir

Penjelasan

{                                  }  # Anonymous codeblock
                     xx 2**$_         # Repeat 2**len(n) times
            .[0]*=-1                  # Negate the first element
 $_.=rotate(        )                 # Rotate the list by that value
                             ;!.[0]   # Return if the first element is 0
Jo King
sumber
2
Keadaan mesin Foo juga mencakup lokasi penunjuk, bukan hanya tanda dari setiap sel.
Magma
1
Sketsa bukti untuk mesin Foo dengan tape a_1 ... a_n 0. Pertimbangkan n-kubus dari tanda-tanda setiap sel dengan tepi terarah (= iterasi dari Foo) antara simpul (= status), mengunjungi simpul yang sama melalui setiap loop tepi akan menghasilkan IP berada di posisi yang sama dengan permulaannya. . Bukti: Dalam satu lingkaran, IP bergerak di setiap dimensi beberapa kali, yaitu IP berubah dengan k × (a_j + (-a_j))% n ≡ 0 untuk setiap dimensi, karenanya selalu kembali ke posisi yang sama, hanya pernah melihat 1 state dari n state untuk setiap vertex, yaitu total maksimum 2 ^ n state (= jumlah simpul kubus).
Kritixi Lithos
n2n.lHaig(n)/n
3

05AB1E , 14 13 byte

goFć©(š®._}®_

Cobalah 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!

Nick Kennedy
sumber
Oh bagus, jadi itulah jawaban Jelly Anda! Sangat bagus menggunakan rotate dan ć! 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·Fto «v( Coba online. )
Kevin Cruijssen
Dan satu tambahan -1 dengan menggunakan ©®alih-alih DŠs: «vć©(š®._}®_( Coba online. )
Kevin Cruijssen
Seperti yang dicatat oleh Arnauld pada jawaban Python Anda, mengulang dua kali panjangnya tidak cukup. Jadi, Anda dapat mengubah «vke goF.
Kevin Cruijssen
@KevinCruijssen terima kasih
Nick Kennedy
3

Java 8, 78 79 73 byte

a->{int k=0,l=a.length,i=0;for(;i++<1<<l;k%=l)k-=(a[k]*=-1)%l-l;k/=a[k];}

Port 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 zerokesalahan saat itu bisa berhenti, atau tidak ada kesalahan jika tidak.

Cobalah online.

Penjelasan:

a->{                   // Method with integer-array as parameter and no return-type
  int k=0,             //  Index integer, starting at 0
      l=a.length,      //  The length `l` of the input-array
  i=0;for(;i++<1<<l;   //  Loop 2^length amount of times:
          k%=l)        //    After every iteration: take mod `l` of `k`
    k-=                //   Decrease `k` by:
       (a[k]*=-1)      //    Negate the value at index `k` first
                 %l    //    Then take modulo `l` of this
                   -l; //    And then subtract `l` from it
                       //  (NOTE: the modulo `l` and minus `l` are used for wrapping
                       //  and/or converting negative indices to positive ones
  k/=a[k];}            //  After the loop: divide `k` by the `k`'th value,
                       //  which will result in an division by 0 error if are halting
Kevin Cruijssen
sumber
2
Hanya ingin tahu, apakah Anda diizinkan untuk mengambil panjang sebagai argumen tambahan? Default untuk posting IO pada meta tidak mengatakan demikian, dan satu-satunya alasan jawaban kedua saya memakan waktu lama adalah karena dibutuhkan dalam int*(dari codegolf.meta.stackexchange.com/a/13262/84206 )
Perwujudan Ketidaktahuan
@EmbodimentofIgnorance Ah, ketika saya melihat jawaban Anda, saya berasumsi ada semacam aturan meta yang memungkinkan panjang untuk diambil sebagai input tambahan, tetapi itu hanya berlaku untuk pointer. Terima kasih telah memberi tahu saya. Saya telah menghapus parameter panjang (tapi masih menggunakan error / no-error untuk menentukan hasilnya).
Kevin Cruijssen
3

Haskell , 79 byte

s x|m<-length x,let g(n:p)=(drop<>take)(mod n m)(-n:p)=iterate g x!!(2^m)!!0==0

Cobalah online!

Pengembalian Trueuntuk mesin penghenti, dan Falsesebaliknya. Input dalam bentuk daftar, dengan 0mewakili keadaan terputus-putus.

Diasumsikan versi GHC lebih besar dari 8,4 (dirilis Februari 2018).

B. Mehta
sumber
2

JavaScript (Node.js) , 71 67 byte

x=>{for(p=l=x.length,i=2**l;i--;)p+=l-(x[p%l]*=-1)%l;return!x[p%l]}

Pada dasarnya sama dengan jawaban C # .NET .EmbodimentOfIgnorance

Simpan 4 byte berkat @Arnaud

Cobalah online!

JavaScript (Node.js) , 61 byte

x=>{for(p=l=x.length,i=2**l;i--;p+=l-(x[p%l]*=-1)%l)x[p%l].f}

Versi ini digunakan undefinedsebagai simbol penghentian dan melempar TypeError: Cannot read property 'f' of undefinedketika mesin berhenti dan berhenti dengan tenang ketika mesin tidak berhenti.

Cobalah online!

IQuick 143
sumber
1

Scala , 156 byte

IMO masih golf, tapi saya baik-baik saja dengan itu untuk saat ini. Pengembalian 0untuk yang tidak berhenti Foodan 1untuk berhenti Foo. Mengambil input asebagai Array[Int], jadi hdiambil sebagai 0.

var u=Seq[Array[Int]]()//Keep track of all states
var i=0//Index
while(u.forall(_.deep!=a.deep)){if(a(i)==0)return 1//Check if we are in a previously encountered step ; Halt
u:+=a.clone//Add current state in the tracker
var k=i//Stock temp index
i=(a(i)+i)%a.length//Move index to next step
if(i<0)i+=a.length//Modulus operator in Scala can return a negative value...
a(k)*=(-1)}//Change sign of last seen index
0//Returns 0 if we met a previous step

Cukup lama untuk dijalankan (sekitar 4 detik untuk semua kasus uji) karena beberapa pencarian array penuh yang saya lakukan, ditambah .deepyang membuat salinan ... Tetapi Anda masih dapat mencobanya secara online.

V. Courtois
sumber
1

Perl 5 -ap , 88 byte

for(;$F[$i]&&!$k{"$i|$F[$i]"};$i=($i+$F[$i])%@F){$k{"$i|$F[$i]"}=1;$F[$i]*=-1}$_=!$F[$i]

Cobalah online!

Xcali
sumber
1

Attache , 40 byte

Not@&N@Periodic[{On[0,`-,_]&Rotate!_@0}]

Cobalah online!

Penjelasan

{On[0,`-,_]&Rotate!_@0}

Ini melakukan iterasi tunggal dari mesin Foo; itu meniadakan anggota pertama, kemudian memutar array dengan elemen pertama (asli, tidak dinegasikan) dari array.

Periodicakan 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.

&Nadalah cara golf untuk mendapatkan elemen pertama dari array numerik. Kemudian, Notkembalikan trueuntuk 0 (mesin penghenti) dan falseuntuk yang lainnya (mesin non penghenti).

Conor O'Brien
sumber
1

Arang , 28 byte

≔⁰ηFX²L諧≔θ籧θη≧⁻§θη绬§θη

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.

FX²Lθ«

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.

Neil
sumber
0

Stax , 11 byte

Ç₧┬òE▐tµ|⌡1

Jalankan dan debug itu

Dibutuhkan input dalam bentuk array integer, dengan 0 mewakili penghentian.

Ini output 1untuk berhenti dan 0untuk mesin non-berhenti.

rekursif
sumber
0

Pyth , 12 byte

!hu.<+_hGtGh

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 0karena di situlah rekursi berhenti. Untuk program yang tidak berhenti, daftar tidak akan dimulai dengan 0, tetapi berada dalam keadaan di mana prosesnya akan berkala dan karena itu mesin Foo tidak akan berhenti.

Tuan Xcoder
sumber