# The halting problem of Turing machines in view of enumeration of initial tape configurations

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.)

• 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). Dec 14, 2015 at 19:14