0
$\begingroup$

Suppose there's a program A that decides whether or not every program halts.

Then we could construct program B that invokes A and does the opposite. Do I halt? If so, loop. Do I loop? If so halt.

That shows we cannot construct program B.

HOWEVER, that assumes B can be embedded in A.

Could there exist a program B that decides all programs of length N or less - their halting, such that B is greater in length than N?

In other words, the "halter decider" is necessarily bigger than the programs it's proving.

Trivially, there exists a computer program that decides the halting of all programs of length 100 or less. There's 2^100 programs of length 100 or less (assuming programs are encoded in base-2). Therefore there's a base-2 number with length 2^100 where each bit corresponds to whether or not the program halts.

Thus, you can solve the halting problem for any arbitrary length or less.

In general, given a finite set M of Turing Machines, there exists a Turing Machine that decides the halting problem for M

Anything wrong with this logic?

$\endgroup$
1
  • 2
    $\begingroup$ As long as you include in this finite encoding also the input on which you run the machine, then yes. In fact, not only is there a TM that decides it, there is a finite automaton that decides it, since it's essentially a finite language (or rather, a finite promise problem). $\endgroup$ – Shaull Feb 25 at 14:40
2
$\begingroup$

Your logic is somewhat correct. I will start by discussing the new definition you tried to give for the halting problem, and then move on to explain the finite set of TMs.


Halting problem, with size less than the TM that solves it

This idea is certainly interesting, but it has some inherent problems with it.

First is a syntax problem. What language is here? Since $N$ is not bounded, this cannot be expressed as a usual computational problem with TMs. In order to formalize this you might want to create a new definition.

The second problem, is a bit more subtle: How do you define the "size" of a TM? For example, if you decide to define it as the running time of the algorithm, then obviously is such a $B$ for every $N$ (just do a loop that does nothing for $N-1$ steps and after that accept). But if you define it as the length of the code plus the length of the inputs, then you can show that there is no such $B$ for big enough $N$. (the formal halting problem gets two inputs $A,X$ where $A$ is a program code and $X$ is some string, and you create a new TM that simulates it with only one input instead of two, reducing the size)

Those examples are obviously two opposite sides of a wide spectrum. You want to formally define the problem and the definition of the size of a TM before you can think of whether or not its possible.


Finite set of TM

The formalization of the halting problem $H$ is as follows: $H=\{\langle M, x \rangle : M \text{ is a TM }\land M(x)\text{ halts}\}$

With this definition, even if you restrict it so $M$ would be in a predefined finite set of TMs, and even if this set contains only one TM, this is an undecidable problem! The counterexample, is $U$ - the universal TM. We will use a slightly different version of it, since we dont need its full power. $U$ (in this context) gets one input, which is a string representing a TM, and $U$ simulates this TM with the input $\epsilon$. Then solving whether $U$ halts on some input or not, is undecidable, since its equivalent to the problem called $H_\epsilon$ which is known to be undecidable.

However, if you would restrict the $H_\epsilon$ problem itself for only a finite set of TMs, the problem becomes decidable, and even more! It becomes a regular language. This is because for each $TM$ in this finite set we know beforehand whether or not it halts, and we dont have to actually do any computation apart from assigning each of those $TM$ the correct label we already know.

$\endgroup$
10
  • $\begingroup$ "syntax problem" Use any Turing-complete formalization. There is a mapping of all Turing machines to natural numbers. 1, 2, 3, ... are Turing machines. Same idea as "Godel numbering" $\endgroup$ – Jesus is Lord Feb 25 at 14:59
  • $\begingroup$ Regarding "size" you could encode input with Turing machine, as you've said. You could also rewrite question as "Does this program halt on ANY input?" or "Does this program halt on ALL inputs" or "Does this program halt on inputs I with property P?" $\endgroup$ – Jesus is Lord Feb 25 at 15:07
  • $\begingroup$ The "syntax problem" I am referring to, is that a language cannot be defined by the TM that solves it and also define that TM at the same time. By this I mean that the usual way to define a language must be independent of your choice for $B$, which is not the case here, since you require it to work only on inputs smaller than $B$. $\endgroup$ – nir shahar Feb 25 at 15:11
  • $\begingroup$ "and even if this set contains only one TM, this is an undecidable problem!" Not following. What if the single Turing machine has one state, an accepting state, and always transitions to its start state? It halts on all inputs $\endgroup$ – Jesus is Lord Feb 25 at 15:12
  • 1
    $\begingroup$ It obviously depends, but I only wanted to give one counterexample to your intuition. Indeed, if the singe TM immediately accepts always, then the problem is obviously easy. But its not always like that $\endgroup$ – nir shahar Feb 25 at 15:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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