Selesaikan sebagian masalah penghentian untuk brainf ***

Untuk memecahkan Masalah Pemutusan Anda diberikan deskripsi suatu program, dan harus menentukan apakah program tersebut akan selesai atau tidak. Anda tidak pernah dapat melakukan ini untuk semua program. Namun untuk program-program seperti (dalam brainf *** ):

>

Ini jelas akan berhenti, dan untuk program-program seperti:

+[]

Jelas tidak akan. Tantangan Anda adalah untuk "memecahkan" masalah penghentian sebanyak mungkin program. Program-program ini tidak akan menggunakan .atau ,, dan tidak akan memiliki input atau output. Anda akan diberikan deskripsi program dan harus menampilkan "Berhenti", "Tidak berhenti", atau "Tidak Diketahui". Ketika program Anda menghasilkan "Hentikan" atau "Tidak berhenti", Anda telah menyelesaikan program input. Berikut ini beberapa persyaratan.

1. Itu harus menyelesaikan setidaknya sejumlah program yang tak terbatas.
2. Untuk setiap program yang dipecahkannya, solusinya harus benar.
3. Anda hanya dapat menampilkan 1 dari 3 pilihan di atas.
4. Anda dapat berasumsi bahwa komputer yang berjalan memiliki waktu dan memori yang tidak terbatas, sehingga XKCD 1266 tidak akan berfungsi (rekaman itu tidak terbatas).
5. Tidak ada sumber daya eksternal.
6. Anda mungkin tidak menggunakan bahasa pemrograman yang benar-benar dapat memecahkan masalah penghentian .

Anda mungkin memiliki program sampingan non-kode-golf yang mengambil string yang merupakan program, dan menghasilkan semacam pohon sintaksis abstrak jika Anda mau. Catatan, itu tidak benar-benar mencetak skor per se, tetapi bagaimana menentukan apakah satu program mengalahkan yang lain.

1. Jika program A memecahkan jumlah tak terbatas dari program yang B tidak, tetapi B hanya memecahkan hingga atau tidak ada program yang diselesaikan A, A secara otomatis menang.
2. Kalau tidak, program dengan karakter paling sedikit akan menang. Jangan hitung spasi atau komentar, jadi jangan mengaburkan kode Anda.

Kiat: Pengatur waktu tidak akan berfungsi. Anda lihat, untuk setiap waktu T dan mesin yang diberikan, ada N, sehingga semua program lebih lama dari yang harus mengambil lebih dari waktu T. Ini berarti bahwa penghitung waktu hanya dapat mencapai solusi dari sejumlah program terbatas, dan, seperti yang Anda lihat di atas, menyelesaikan sejumlah program terbatas tidak membantu.

Python, kode spageti yang tidak dikerami

Oh sayang.

def will_it_halt(instructions):
    tape_length = 1
    LOOP_BOUND = 1000
    registry = [0] * tape_length
    pos = 0

    jumpbacks = []
    reached_states = set()

    pos_instructions = 0
    while True:
        letter = instructions[pos_instructions]
        if letter == "+":
            registry[pos] = (registry[pos] + 1) % 256
        elif letter == "-":
            registry[pos] = (registry[pos] - 1) % 256
        elif letter == ">":
            pos += 1
            if pos >= tape_length:
                registry += [0]*tape_length
                tape_length = len(registry)
        elif letter == "<":
            pos -= 1
            if pos <= 0:
                registry = [0]*tape_length+registry
                tape_length = len(registry)
                pos += tape_length
        elif letter == "[":
            if registry[pos] == 0:
                nests = 1
                while nests:
                    pos_instructions += 1
                    if instructions[pos_instructions] == "[": nests += 1
                    elif instructions[pos_instructions] == "]": nests -= 1

                if jumpbacks == []:
                    reached_states.clear()

            else:
                jumpbacks.append(pos_instructions-1)

        elif letter == "]":
            stripped_registry = [str(x) for x in registry if x != 0]
            translated_pos = pos - (len(registry) - len(stripped_registry))
            state = (translated_pos, pos_instructions, ".".join(stripped_registry))
            if state in reached_states: return "Does not halt"
            elif len(reached_states) > LOOP_BOUND: return "Unknown"
            else:
                reached_states.add(state)
                pos_instructions = jumpbacks.pop()
        pos_instructions += 1
        if pos_instructions >= len(instructions): break
    return "Halts"

Solusi yang cukup kasar untuk masalah: jalankan saja kode bf. Kami menganggap panjang rekaman itu panjang sewenang-wenang dan sel-sel individu membungkus pada 256. Pada akhir setiap loop, kami menyimpan keadaan rekaman itu dengan satu set. Negara adalah dari bentuk (posisi kita pada rekaman itu, posisi kita pada instruksi, seperti apa rekaman itu dengan memimpin 0's dilucuti).

Jika kita menyimpan keadaan yang sama dua kali, maka kita berada di suatu tempat dalam loop tak terbatas, sehingga program tidak berhenti. Jika kami menyimpan lebih dari 1.000 negara, maka potong kerugian dan kembalikan tidak diketahui. Setelah kami meninggalkan satu loop kami memeriksa untuk melihat apakah kami tidak ada dalam loop yang lebih besar. Jika tidak, kita tidak akan pernah melihat status sebelumnya lagi (paling tidak, posisi instruksi akan selalu berbeda!) Sehingga kita dapat menghapus set status.

Ini harus secara akurat menentukan setiap program BF yang loop tidak lebih dari 1.000 iterasi, serta banyak program yang mengulang keadaan sebelum 1.000 iterasi dalam satu lingkaran. Namun tidak semuanya: sesuatu seperti "{1 juta + ada di sini} [-]> + [+ -]" akhirnya mengulangi keadaan, tetapi loop [-] melewati 1.000 iterasi terlebih dahulu.

Beberapa contoh:

>+>->+>-

Tidak ada loop, sehingga mencapai ujung dan berhenti.

+[+]

Loop berakhir setelah 256 iterasi, sehingga mencapai akhir dan berhenti.

+[+-]

Akhirnya mengulangi keadaan (0,5, "1"), sehingga tidak berhenti.

+[->+]

Ini tidak mengulangi status apa pun tetapi perulangan tidak pernah berakhir, jadi ini harus mencetak "tidak dikenal". Tapi programnya curang di sini. Alih-alih menyimpan posisi pada rekaman, itu menambah offset antara registri asli dan yang dilucuti. Jika semua loop dilakukan adalah menerjemahkan kaset dengan beberapa spasi, maka itu akan terus menerjemahkannya tanpa batas waktu (seperti life glider), jadi kita dapat mengatakan itu tidak berhenti.

+[>+]

Tidak menerjemahkan, tidak mengulangi status apa pun, mencetak tidak dikenal.

+++++++++++[-]

Ini berhenti, tetapi akan mencetak "tidak dikenal" jika LOOP_BOUND berusia 10.

Ada beberapa cara untuk membuat ini lebih pintar. Anda jelas dapat meningkatkan LOOP_BOUND untuk mengurangi jumlah yang tidak dikenal. Anda bisa memiliki penanganan yang lebih pintar dari loop bersarang. Anda mungkin bisa melakukan sesuatu yang mewah dengan nomor BB dan ukuran loop untuk lebih mendeteksi jika ada sesuatu yang berhenti, tapi saya tidak cukup baik di CS atau di Python untuk dapat melakukan itu.

GolfScript (23 karakter, jawaban benar tak terbatas)

'[]'&!
# 0 if there are brackets, so Unknown
# 1 if there are no brackets, so no looping, so definitely halts
'UnknownHalts'7/=

Awk

Perpanjangan kecil dalam kekuasaan dari dua contoh. Jika suatu program tidak mengandung loop sama sekali, maka tidak ada keputusan, itu masih jelas bertekad untuk berhenti. Karena kami mengasumsikan validitas program, kami juga mengasumsikan tanda kurung seimbang dan karenanya hanya perlu mencari satu tanda kurung.

BEGIN{RS=""}
!/\[/{print "Halts"; exit}
END{print "Unknown"}

Untuk yang kedua, itu harus memeriksa dulu apakah loop sama sekali, jadi kita harus mensimulasikan kode garis lurus sebelum loop. Kemudian, jika loop kembali ke sel yang sama (mis. Jumlah >s sama dengan jumlah <s di dalam loop), dan ia tidak melakukan incs atau decs pada sel ini (mis. Untuk setiap awalan posisi seimbang dari keseimbangan loop body, tidak ada instance +atau -sebelum berikutnya <atau >, maka sel tidak dimodifikasi). Menerapkan bagian ini mungkin membutuhkan waktu lebih lama. Ooh, tunggu, untuk bagian pertama dari memeriksa apakah loop sama sekali, kita bisa mengambil ide yang sama dan mencari program pre-loop untuk sufiks seimbang dan bersikeras bahwa ada a +atau -(tidak seimbang).

Haskell

Berikut adalah contoh jawaban yang sangat sederhana. Jangan ragu untuk memasukkannya ke dalam jawaban Anda (karena Anda memasukkan beberapa tes dalam jawaban adalah ide yang bagus.)

main=do
    p<-getLine
    if take 3 p == "+[]"
        then putStr "Does not halt"
        else putStr "Unknown"

Ini pada dasarnya melihat apakah ada loop di awal. Jika loop persis itu tidak terjadi di awal, itu hanya menyerah. Bahkan tidak berhasil ++[]. Itu memang memecahkan sejumlah program yang tak terbatas, dan selalu benar ketika menyelesaikannya.