Apa mesin Turing terkecil di mana tidak diketahui apakah berhenti atau tidak?

31

Saya tahu bahwa masalah penghentian tidak dapat diputuskan secara umum tetapi ada beberapa mesin Turing yang jelas berhenti dan beberapa yang jelas tidak. Dari semua mesin turing yang mungkin, apa yang terkecil di mana tidak ada yang punya bukti apakah itu berhenti atau tidak?

halting-problem Harun
sumber

10

Jawabannya tergantung pada spesifikasi model mesin (jumlah simbol, dll.). Menurut artikel Wikipedia tentang Busy Beaver ada mesin 2-simbol 5-sate yang tidak diketahui apakah berhenti atau tidak.

Kaveh

1

Perhatikan bahwa pertanyaan Harun bukanlah tentang kepantasan bahasa yang diberikan, tetapi benar-benar adanya bukti bahwa mesin Turing tertentu berhenti. Untuk mesin Turing apa pun, masalah penghentiannya "" (apakah mesin ini benar-benar berhenti pada input yang kosong) adalah "decidable": ia adalah Ya atau Tidak, dan kedua bahasa {Ya} dan {Tidak} dapat ditentukan. Ini sangat berbeda dari apakah seseorang memiliki bukti bahwa mesin berhenti atau tidak. Aaron, jika Anda benar-benar mengatakan "apa paling kecil sehingga bahasa berhenti pada tidak dapat ditentukan," bisakah Anda mengedit pertanyaan Anda?

M

$M$

{w ∣ M

$\{w \mid M$

w}

$w\}$

Michaël Cadilhac

1

@ MichaëlCadilhac Masalah penghentian biasanya diartikan sebagai, "Diberikan mesin dan input , apakah

berhenti untuk input

?" tidak "Diberi mesin , apakah berhenti untuk semua input?"

M

$M$

w

$w$

M

$M$

w

$w$

M

$M$

M

$M$

David Richerby

@ DavidVicherby: Bagi saya, masalah penghentian adalah bahasa mesin (kode) yang berhenti pada input kosong. Jika itu bukan makna yang dimaksudkan di sini, saya pikir itu harus ditentukan untuk menghilangkan kemungkinan kebingungan (ok, saya).

Michaël Cadilhac

berbagai cara mempelajari masalah itu valid & saling terkait & memang ada perbedaan dalam membedakannya yang tidak dimiliki si penanya.

vzn

38

Mesin Turing terbesar yang masalah penghentiannya dapat ditentukan adalah:

(di mana adalah himpunan mesin Turing denganstatus dansimbol ). $TM(2,3), TM(2,2), TM(3,2)$ $TM(k,l)$ $k$ $l$

The decidability dari dan adalah pada batas dan sulit untuk menetap karena tergantung pada dugaan Collatz yang merupakan masalah terbuka. $TM(2,4)$ $TM(3,3)$

Lihat juga jawaban saya pada cstheory tentang mesin Turing seperti Collatz dan " mesin Turing Kecil dan kompetisi berang-berang yang digeneralisasi secara umum " oleh P. Michel (2004) (di mana diduga bahwa juga dapat dipilih). $TM(4,2)$

Komentar Kaveh dan jawaban Mohammad benar, jadi untuk definisi formal dari mesin Turing standar / non-standar yang digunakan dalam hasil seperti ini lihat Turlough Neary dan Damien Woods bekerja pada mesin Turing universal kecil, misalnya Kompleksitas mesin Turing universal kecil: sebuah survei (Aturan 110 TM sangat universal).

Marzio De Biasi
sumber

2

Isn't the halting problem for any given finite set of Turing machines always decidable? Since there are only finitely many machines in

T M (4, 2)

$TM(4, 2)$ , it must be possible to construct a lookup table which correctly says which machines halt and which ones don't, and so there must be a Turing machine which uses this lookup table to correctly answer the question.

Tanner Swett

2

@TannerSwett: here we consider the halting set

{⟨ M, x ⟩ ∣ M halts on x}

$\{\langle M,x \rangle \mid M \text{ halts on } x\}$ or, in other words, for which Turing machines

H A L T_{M} = {x ∣ M halts on x}

$HALT_M = \{ x \mid M \text{ halts on } x\}$ is decidable (see Michel's paper).

Marzio De Biasi

32

I would like to add that there are some Turing Machines for which the Halting problem is independent of ZFC.

For instance take a Turing machine which looks for a proof of contradiction in ZFC. Then if ZFC is consistent, it won't halt, but you cannot prove it in ZFC (because of Gödel's second incompleteness theorem).

So it is not only a matter of not having found a proof yet, sometimes proofs don't even exist.

Denis
sumber

ZFC? What does ZFC mean? I just can't figure it out from the context.

Acapulco

7

@Acapulco lmgtfy.com/?q=zfc&l=1

Sasho Nikolov

Lol! ok. I got lmgtfy'ed. Touchè. Didn't think it would be initials that would immediately and uniquely relate to this topic. In any case I don't think it hurts to add a courtesy "ZFC (Zermelo–Fraenkel set theory)" clarification the first time its mentioned, also to avoid ambiguity in case there is? :)

Acapulco

16

@Acapulco, please see tour and help center. Any theoretical computer scientist would know what ZFC stands for so there is not really a need for a clarification.

Kaveh

1

In particular, note the recently discovered

2

$2$ -symbol machines with ZFC-independent halting problem, discussed here (7918 states), here and here (1919 states). The number of states is almost certain to be decreased further.

r.e.s.

5

No one has a proof whether Universal Turing machine halts or not. In fact, such proof is impossible as a result of the undecidability of the the Halting problem . The smallest is a 2-state 3-symbol universal Turing machine which was found by Alex Smith for which he won a prize of $25,000.

Mohammad Al-Turkistany
sumber

4

Note, however, that, according to the Wikipedia page cited, the proof of universality is disputed. Also, this is not the standard model of Turing machines: the allegedly universal machine has no halt state so cannot simulate any machine that halts, at least in the standard sense of what a universal Turing machine does.

David Richerby

2

@DavidRicherby: I think that the weakly-universality of the rule 110 is quite accepted: it requires two different words repeated on the left and right of the input, and the halting condition is the generation of a special glider (generated if and only if the simulated machine halts). See Matthew Cook's "Universality in elementary cellular automata".

Marzio De Biasi

-4

an inexactly phrased but reasonable general question that can be studied in several particular technical ways. there are many "small" machines measured by states/symbols where halting is unknown but no "smallest" machine is possible unless one comes up with some justifiable/quantifiable metric of the complexity of a TM that takes into account both states and symbols (apparently nobody has proposed one so far).

actually research into this problem related to Busy Beavers suggests that there are are many such "small" machines lying on a hyperbolic curve where $x \times y$ , $x$ states and $y$ symbols, is small. in fact it appears to be a general phase transition/boundary between decidable and undecidable problems.

this new paper Problems in number theory from busy beaver competition 2013 by Michel a leading authority exhibits many such cases for low $x,y$ and shows the connection to general number theoretic sequences similar to the Collatz conjecture.

vzn
sumber

2

It's not necessary to establish a metric taking into account symbols and states. Once there are two symbols on the tape, it's clear that the halting problem is undecidable for almost all numbers of states -- as I recall, it's possible to write a universal TM with only five states. If we knew the exact boundary of decidability, I'm sure it would be easy to describe that boundary in terms of (#states,#symbols) pairs.

David Richerby

the busy beaver research indeed involves finding proofs for whether TMs halt for initial setups with small # of states, symbols; there are resolvable cases. if one wants the "smallest" anything one must create a precise metric that measures "small". the pt above is that a metric that only involves states or symbols alone can be regarded as misleading as far as representing the known boundary which involves both (and machines not known to be universal). the undecidability boundary in this research is not "easy" to specify in terms of anything at all, that is its fundamental nature....

vzn

1

Nobody proposed a metric based on only #states or only #symbols. And the (#states,#symbols) boundary is trivial to describe. For one state, it is decidable. For

2 \leq i \leq 4

$2\leq i\leq 4$ states, it is decidable for alphabets of size at most

k_{i}

$k_i$ , where

k_{2}

$k_2$ ,

k_{3}

$k_3$ ,

k_{4}

$k_4$ are unknown constants. For five states, it is undecidable (except, maybe, for alphabets of size 1). Describing the boundary is trivial; the only non-trivial part is figuring out the values of

k_{2}

$k_2$ ,

k_{3}

$k_3$ ,

k_{4}

$k_4$ .

David Richerby

nobody proposed any metric at all so far. no important boundary in this area is "trivial to describe" & one would expect that scenario would be impossible via Rices thm. this seems to show a lack of familiarity with the research & the cited ref which is interested in resolvability of inputs for machines that are smaller than those known to be universal (and conjectured to not be universal). your comments seem to focus on universal vs nonuniversal machine boundaries which is not the same as the busy beaver decidability boundaries being explored eg in the cited refs (both above & Marzio's).

vzn

Doesn't the fact that I just described it in a Stack Exchange comment imply that it's trivial to describe? The point about universality is that it gives upper bounds for the boundary: if you can implement a universal machine with

x

$x$ states and

y

$y$ symbols, the halting problem for

x

$x$ -state,

y

$y$ -symbol TMs is clearly undecidable.

David Richerby

Apa mesin Turing terkecil di mana tidak diketahui apakah berhenti atau tidak?

Jawaban: