3
$\begingroup$

As far as I know, presentations of the (general) halting problem (cmp. Wikipedia) are referring explicitly to an ennumeration of (applicable) programs. For the purpose of my questions let's consider specificly any programs for one-head, two-symbol Turing machines with sufficient memory to store the instructions prescribed by the program and any (internal) state reached in the course of executing the program.

Such an enumeration of applicable programs could be symbolically written as

$$ p : \{ \mathsf{TM_{\text{(1 head, 2 symbols)}}} \} \leftrightarrow \mathbb N.$$

(The mapping is one-to-one since enumeration is supposed to be without gaps, and there are infinitely many Turing machine programs to be enumerated. For definiteness, the set $\mathbb N$ here denotes the whole numbers, including $0$.)

I am interested in the consequences of the input (i.e. specificly the contents of the tape, in reference to the machine head, at the start of program execution) being explicitly encoded through an enumeration as well; symbolically

$$ s : \{ \text{ starting tape configurations } \} \leftrightarrow \mathbb N;$$

specificly for instance, for input $\text{ tape contents }$ with non-blank fields on positions $1 \le a \lt b \lt c ... \lt l$ to the left of the Turing machine head and on positions $0 \le z \lt y \lt x ... \lt r$ to the right of the head (and if applicable on position $0$ directly under the head in starting position) then

$$ s[~\text{tape contents}~] := (4^a + 4^b + 4^c ... +~4^l)/2 + 4^z + 4^y + 4^x ... +~4^r.$$

(The completely blank tape is accordingly encoded as number $0$.)

My question:
Given the above description, can the non-existence of a halting program ("DoesItHalt?") be proven regardless of the specific enumeration $p$ of Turing machine programs? And if so, how exactly?


As an illustration of possible difficulties in trying to argue that a Turing machine program "DoesItHalt?" doesn't exist one might perhaps consider the composition

BadH := EncodeInput | DuplicateArgument | DoesItHalt? | ContrarianActor

which should have the value $p[$ BadH $]$ in the enumeration of programs,
running on input "BadI" which would be selected exactly such that

$p[$ BadH $] = s[$ BadI $]$;

where

  • EncodeInput is supposed to be a specific program implementing the enumeration $s$,

  • DuplicateArgument is a simple program to prepare the two arguments required for a (meaningful) subsequent execution of DoesItHalt?, and

  • ContrarianActor is a simple program whose action is just the opposite of the intended meaning of DoesItHalt?'s result.

Then it would be premature to conclude a contradiction; that program DoesItHalt? didn't function as correct halting program because the program BadH, being run on the inital tape configuration BadI, is thought to act eventually just contrary to the intended meaning of the presumed result of program DoesItHalt? evaluating (running on) the two argument values $p[$ BadH $]$ and $s[$ BadI $]$. Because:

Already the (apparently necessary) program part "EncodeInput" is questionable: It is supposed to terminate when starting on any initial tape configuration with a finite number of non-blank fields (in order to return its enumeration value). But therefore it also returns the exact same result when starting on any "suitably extended" initial tape configuration with some (still finite) additional non-blank fields "sufficiently further out". The correct enumeration values of any such "suitably extended" initial tape configuration cannot be returned by the specific "EncodeInput" program.

Then why not enumerate the specific "BadH" program of the example above precisely by such an "inaccessible" value (which obviously is not being calculated by program part DuplicateArgument either); thus defeating the attempt of arriving at a contradiction in this specific case. (Obviously, this would have to be accomodated by a suitable enumeration of all programs.)

$\endgroup$
2
$\begingroup$

The Halting problem is stated in terms of any admissible numbering. There are effective (i.e. Turing-computable) compilers between all such numberings, so the Halting problems are all the same. That is, in particular not decidable.

There are numberings of all partially-recursive functions for which the Halting problem is decidable -- of course. For instance, give all "yes"-instances even and all "no"-instances odd numbers. Such a numbering would certainly not be admissible; in this case because it would not be partially recursive.

Thus, it comes down for you to show that your numbering is admissible or not. If not, the Halting problem may be decidable but the numbering would be ... not very useful.

$\endgroup$
  • $\begingroup$ Raphael: +1; your answer is certainly insightful, even though it seems to address my attempt at "illustrating a difficulty" rather than my actual question. (How do "admissable numbering" and "computable function" even relate to "initial tape configuration"?...) My lesson: not to focus on enumerations of the TM programs differing from the obvious/standard/canonical one (since there should exist Translator programs), but on "difficult" enumerations of initial tape configurations (and not to specify a simple one, like $s$, outright). $\endgroup$ – user12262 Dec 14 '15 at 19:14
  • $\begingroup$ @user12262 Well, to be honest, I only skimmed your question. I thought that your question came down to this; if it does not help you, we'll have to wait for other answers. :) $\endgroup$ – Raphael Dec 14 '15 at 21:40

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.