Consider a Turing machine with just one head and one tape (on which the head may move left, move right, or remain stationary), and with just two symbols ("blank" and "non-blank"). The programs for such a fairly simple Turing machine can be enumerated systematically (with only variations which seem quite insignificant, however). There should be $(6 n)^{(2 n)}$ different programs with $n$ states, which may be thought given as transition tables. (There shall not be made an explicit declaration of one or more "halting states"; but the possibility of a specific program halting, if at all, should only be implicit by the transition table having one or more "identity transitions".)

Call $$ p : \{ \text{programs for } \mathsf{TM_{\text{(1 head, 2 symbols)}}} \} \rightarrow \mathbb N$$

such a suitable "obvious" and "standard" enumeration of applicable Turing machine programs. (For definiteness, the set $\mathbb N$ here denotes the positive integers, with the smallest number $1$ enumerating the "program without any state".)

Properties of enumeration $p[~]$ shall include that

$$p[~\text{program_X}_{\text{(with }k + 1 \text{ states)}}~] \gt p[~\text{program_Y}_{\text{(with }k \text{ states)}}~],$$

$$p[~\text{program_X}_{\text{(with }k + 1 \text{ states)}}~] - p[~\text{program_Z}_{\text{(with }k - 1\text{ states)}}~] \gt (6 k)^{(2 k)},$$

and that a composition (concatenation, pipe) of enumerated programs is an enumerated program itself, too; obviously with larger index value than any of its "parts".

There is also a straight-forward specific enumeration given to all (finite) initial tape configurations (i.e. the contents of the fields of the tape) on which a Turing machine may happen start to execute its program; namely

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

where 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$, i.e. on the starting field of the head)

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

(The completely blank initial tape is thus assigned the number $1$. Anticipating considerations following below it is notable that any configuration with $q \gt 0$ consecutive non-blank fields, i.e. a "block" of length $q$, e.g. on an otherwise blank tape, is enumerated by an index value larger than $q$.)

Concrete statement of the Halting Problem

With these preparations, a concrete variant of the Halting Problem can be stated:
Is there a program "DoesItHalt?" in the set enumerated by $p$ which, if started on a non-blank field followed on the left by a (finite) consecutive string of $j - 1$ non-blank fields, followed by one blank field and another (finite) consecutive string of $k$ non-blank fields followed by (at least) one blank field (and regardless of any further tape contents towards the left or on the right of the inital head position) will always halt

  • either on a non-blank field if program $p^{(-1)}[~j~]$ being started on initial tape configuration $s^{(-1)}[~k~]$ will eventually halt,

  • or on a blank field if program $p^{(-1)}[~j~]$ being started on initial tape configuration $s^{(-1)}[~k~]$ will never halt ?

(The performance of the hypothetical "DoesItHalt?" program being started on an initial tape configuration of any other description is no concern.)

First attempt at constructing a self-contradictory case

Now, pretending that there is (at least) one positive number $h$ (where obviously $h \gt 1$) such that program "HaltDummy" $:= p^{(-1)}[~h~]$ has the specified properties of the hypothetical "DoesItHalt?" program, I am interested in the construction of a self-contradictory case (from which to conclude that actually no enumerated program satisfies the specifications); by suitable composition of programs, as concrete as possible.

Following well-known examples (e.g. Boolos/Jeffrey "Computability and Logic", Fig. 5-3) consider therefore the program composition

"BlockDuplicator | HaltDummy | ContrarianActor",


  • the BlockDuplicator duplicates whichever finite block of non-blank fields to the left of its starting field, leaving a blank between the resulting two blocks and halting where it started (possibly having erased some fields beyond the left end of the result, and towards the right of the starting field). This specification can be concretely implemented by a program of about a dozen states;

  • the ContrarianActor is a very simple program (just two states) whose action is just the opposite of the intended meaning of DoesItHalt?'s result, and consequently also just opposite to the intended meaning of the supposed output of HaltDummy.

(Anticipating considerations following below let's denote the number of states of this program composition with the constant $C$; where certainly $C \gt 15$.)

But quite obviously running this program composition on any starting tape configuration cannot constitute the desired self-contradictory case for the concrete case to be considered here, because the (hypothetical) DoesItHalt? program and likewise the HaltDummy expect the enumeration value (the "index") $s$ of the initial tape configuration, expressed as a block of $s$ non-blank fields; and not the "plain" tape configuration. (Even if this happens to consist of some "plain" block of non-blank fields. The length of any such block is strictly less than the enumeration value of the tape configuration made up by that block.)

Putting a PreProcessor program in front

Aiming for a construction which might be more promising to yield the desired self-contradictory case it seems necessary to put a suitable PreProcessor ahead of the program composition whose purpose would be

  • to read the given initial tape configuration as input, and

  • to produce a block of $s[$ initial tape configuration $]$ consecutive non-blank fields (with at least one blank field on the left), and

  • to halt (on the right end of that block of $s[$ initial tape configuration $]$ consecutive non-blank fields; the contents of fields further to the right shall be of no concern for a suitable BlockDuplicator).

If the existence of such a suitable PreProcessor, as enumerated program_, can be established then the idea is, of course, to consider running the composition

"PreProcessor | BlockDuplicator | HaltDummy | ContrarianActor" := "CriticalCaseProgram"

on just the tape configuration "JustThisTapeInput" for which

$s[$ JustThisTapeInput $] = p[$ CriticalCaseProgram $]$,

in order to expose that the HaltDummy could not satisfy the requirements of a DoesItHalt? program at least concerning the running of the constructed CriticalCaseProgram on JustThisTapeInput.

But, obviously, there cannot be a universal such PreProcessor program: because any program which halts at all, with some particular output result, after having read some particular finite "stretch" of the given (finite) initial tape configuration will halt with the exactly same output when running on another (but still finite) given initial tape configuration with the exactly same field contents of the same finite "stretch" which is being read, but with different field contents outside this particular "stretch". The output result can have been the correct/intended enumeration value of the given initial tape configuration in at most one case; certainly not in general.

PreProcessor programs of limited scope, and a corresponding inequality

As a work-around we may resort to "PreProcessor-$f$" programs which correctly read initial tape configurations of (at least) $f$ fields to the left and to the right to the head starting field, and output the corresponding correct enumeration value as a block of length $s$. This can still easily be used for constructing the desired self-contradictory case if

  • the enumeration index of the critical case program composition with "PreProcessor-$f$" in the beginning is not larger than the enumeration indices of initial tape configurations which have non-blank fields only within $f$ steps to the left or to the right of the head starting field; i.e. if

  • $p[$ PreProcessor-$f$ | BlockDuplicator | HaltDummy | ContrarianActor $] \le 2^{(2 f + 1)}.$

The number of states of a composition (concatenation, pipe) of program parts is surely just the sum of the states of all parts. For any fixed value $f$ the composition considered as "critical case" therefore has a number of states which can be expressed as the sum of the number of states $n_{\text{P}f}$ of the smallest PreProcessor-$f$ program and the constant number $C \gt 15$. (Constant $C$ may be arbitrarily large, though of course finite, due to the arbitrary, though necessarily finite, number of states ascribed to the HaltDummy program part).

Recalling that there are $(6 n)^{(2 n)}$ programs of $n$ states, it is then required to show that

for all (arbitrarily large) values $f$ and for some fixed value $C \gt 15$ the inequality

$$\sum_{k = 1}^{(n_{\text{P}f} + C)} (6 k)^{(2 k)} \le 2^{(2 f + 1)}$$

is satisfied;

where (to repeat) $n_{\text{P}f}$ is the smallest number of states required for a (one head, two symbol Turing machine) program which scans $f$ fields to the left as well as to the right of the starting field and returns the enumeration value $s$ (as defined above) of the tape configuration consisting of these $2 f + 1$ fields. (To me, this seems quite a difficult problem itself.) Finally:

My question:

Is this inequality known or even expected to hold at all?
(Btw., note that $96^{32} \gt 2^{210}$.)

Note on the Bounty Campaign October 2016:

On October 5th, 2016, I issued a bounty for the above question (100 points; the maximum I could afford at that time). There had been no answer entered here until then.
I was asking explicitly for a "canonical answer", since the Halting Problem may be considered a "canonical problem". And I also added some language to discourage entries along the lines of "It's already been proven (elsewhere) that the assumption of any HaltDummy program leads to contradiction; therefore the described difficulty is inconsequential."

As it happened, later on the same day I found a flaw in the question statement which I tried to correct right away and without pointing out this Edit in the question text itself, as this might have been too distracting. I apologize for any inconvenience or irritation this may have caused.

Today this bounty (period of 7 days) has completed (as the notification put it which I received accordingly); and there still has been no answer entered here. (In the notification it is also stated that "You must award it [the bounty points] to an answer within 24 hours." and I'd have to check whether this is even applicable to answer entries which might still be forthcoming in the 24 hours after completion of the bounty period.)

So: for now I am, and we are, left with the difficulty described in my question.

  • 1
    $\begingroup$ For future questions in similar fashion I can suggest a simplified model where there are only two actions after writing symbol: move left and move right. This is equivalent in power, as 'stay stationary' can always be emulated by going right into a dummy state which always goes left. This makes comparisons easier, as you're only dealing with powers of two. $\endgroup$ – orlp Oct 5 '16 at 18:06
  • $\begingroup$ @orlp: "I can suggest a simplified model where there are only two actions after writing symbol: move left and move right. This is equivalent in power, as 'stay stationary' can always be emulated by going right into a dummy state which always goes left." -- Nice idea; this should "ease" the inequality correspondingly to $$\sum_{k=1}^{(\overline n_{P_f}+\overline C)} (4k)^{(2k)} \le 2^{(2f+1)}$$ (where overline means referring to your simplification); still such that there exists a value $f$ for any (large) values $\overline n_{P_f}$. (Btw., what's the minimal value $\overline C$ ?) $\endgroup$ – user12262 Oct 5 '16 at 18:48
  • $\begingroup$ Please note the recent Edit of my question, namely a (more or less subtle) rephrasing of the inequality statement, which nevertheless constitutes a decisive clarification and even correction. (The inequality statement in my above comment reply to @orlp was correspondingly still more or less subtly incorrect; thanks for prompting me to reconsider. Instead, as reflected in the Edit, the "eased" inequality still needs to hold for any (large) value $f$, with the corresponding value $\overline n_{\text{P}f}$ and with some fixed value $\overline C$ (where surely $\overline C \ge C \gt 15$). $\endgroup$ – user12262 Oct 5 '16 at 23:14

Your Answer

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

Browse other questions tagged or ask your own question.