3
$\begingroup$

This is related to my previous question: Do proofs of $HALT$'s undecidability make it clear that it's practically relevant? I made a mistake of leaving something implicit when I asked it; namely that the machine that decides the bounded version of the halting problem should also be bounded.

Consider the following statement: "given a Turing machine $M$ with less than $k$ states and a word $w$ with less than $k$ symbols, we can decide whether $M(w)$ halts using a machine with less than $k$ states", for some $k$.

I am wondering for what $k$, if any, is this sentence true. Answers don't have to be precise (i.e. "for k = 27"), any approach of thinking about it is welcome.

$\endgroup$
1
  • $\begingroup$ Well there are universal Turing machine with 2 status, so in general this shouldnt be possible for any w $\endgroup$ Oct 17 at 5:55

1 Answer 1

2
$\begingroup$

Consider the following:

Here is a formalization of a proof that halting is undecidable based on universal Turing machines. It uses the following components:

  1. Adding a new state that loops forever to a machine. Each rule where the machine would halt with a $1$ focused on the tape is instead changed to a rule that transitions to the looping state.
  2. A universal Turing machine $U$. This is a machine that when run on input $(M,w)$ behaves equivalently to $M(w)$
  3. A fixed point construction, which modifies a machine $M$ into a machine $μM$ that first adds its own encoding to the tape before behaving like $M$. So, $μM(w)$ is equivalent to $M(w,μM)$. This is a pretty complicated thing to actually build for Turing machines, but there's a theorem that they exist.
  4. A duplicating modification. This one changes $M$ to $ΔM$ so that $ΔM(w,x)$ is equivalent to $M(w,(x,w))$

If we indicate the first transformation as $¬$, then the machine we build is $\hat U = μ(Δ(¬U))$. Then for a machine $H$, we have the following equivalences:

$$\hat U(H) \simeq Δ(¬U)(H,\hat U) \simeq ¬U(H,(\hat U, H)) \simeq ¬H(\hat U, H)$$

and the last execution has the opposite halting behavior from what $H(\hat U, H)$ indicates. So, $H$ fails to decide the halting behavior of $\hat U(H)$.

Now, I don't know the actual size of $\hat U$, because I don't know how much blow-up $μ$ causes. For typical programming languages, that sort of 'Quine' like program would be around double the size of the input, plus some fixed cost. For instance, in Haskell, you can write something similar like:

f g x = let s = "f g x = let s = % in g x (sub s s)" in g x (sub s s)

where sub s t is a function that replaces occurrences of % in s with t surrounded by quotes.1 This is considerably longer than the two occurrences of g, but if the code for g were inlined, it could be longer than the fixed overhead for f. In any case, I'd expect the factor to be worse for Turing machines.

As mentioned in the comment above, there are 2 state UTMs, although other combinations might be more economical. $Δ$ is a fixed, relatively small cost and $¬$ is even smaller. The bottom line, though, is that $\hat U$ has some particular (honestly probably not very large) size, and it is a sort of universal diagonal machine. So there is a state size $k$ for which no machine $H$ can predict what all machines of size $k$ will do when run with an encoding of $H$ as input.

I suspect that the loophole in this argument is that the encoding of $H$ as a word has significantly more symbols than $H$ has states. So, by stating that both the number of states in $M$ and the symbols in $w$ are less than $k$, you are excluding the diagonal case that this argument presents.

However, that also means that in the case of a universal machine like $\hat U$, you are only considering what it does with inputs that correspond to machines with a fraction of the states in $H$. In other words, the idea that a program's halting behavior can only be reliably decided by a significantly longer program is built into your question. And this can't be fixed, or else diagonalization will work.

[1] If you want to inline g, then sub might have to become more elaborate about quoting the substituted string. This is also necessary if you want to include the code for sub and the quotation directly in f. But it's ultimately possible.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.