Skip to main content
2 of 2
corrected spelling
Thomas Benjamin
  • 6.1k
  • 1
  • 25
  • 39

Consider how Turing defined oracles (he being the one who created the notion--this quote is from his paper "Systems of Logic Based on Ordinals" found on pp. 156-7, and pg 154 of Jack Copeland's book, $The$ $Essential$ $Turing$):

"Let us suppose that we are supplied with some unspecified means of solving number-theoretic problems; a kind of oracle as it were. We shall not go into the nature of this oracle apart from saying it cannot be a machine. With the help of this oracle we could form a new kind of machine (call them $o$-machines), having as one of its fundamental processes that of solving a given number-theoretic problem. The moves of the machine are are determned as usual by a table except in the case of moves from a certain internal configuration $\mathfrak o$. If the machine is in the internal configuration $\mathfrak o$ and the sequence of symbols marked with $\mathfrak l$ is then the well-formed formula $A$, the machine goes into the internal configuration $\mathfrak p$ or $\mathfrak t$ according as it is or is not true that $A$ is dual." ['$A$ is dual' means that $A$ satisfies the following property "Every number-theoretic theorem is equivalent to a statement of the form '$A(n)$ convertible to 2 for for every W.F.F. $n$ representing a positive integer' (in Church's $\lambda$-calculus), $A$ being the W.F.F. determined by the theorem"....this simply means that for Turing's purposes, his oracle is interested in determining whether or not $A$ is a number-theoretic theorem--of course this notion can be generalized as follows: given a Goedel number $n$ in the internal configuration $\mathfrak o$, the $\mathfrak o$-machine will go into the internal configuration $\mathfrak p$ or $\mathfrak t$ according as it is or is not true that $n$$\in$$S$, the nature of $S$ to be determined.]

It is this concept that the OP believes to be essentially unsound.

After the OP's elementary error is is discovered and is realized and accepted by the OP, one can still ask the question "Is it still essentially unsound?" The reason one might still say that the notion of oracle is unsound is because the means by which the oracle determines whether '$n$$\in$$S$' or not is not, or cannot be, specified.

I argue that they can, though not in terms (of course) of Turing machines. One should first note that Turing describes an oracle as a "fundamental process" that "cannot be a machine" (i.e. not reducible to a Turing machine). What does this mean? Well, it means (at least to me) that an oracle cannot be defined in terms of a set of quadruples of the form $<$$($$i$$)$ $internal$ $configuration$,$($$ii$$)$ $cell$ $condition$, $($$iii$$)$ $operation$, $($$iv$$)$ $internal$ $configuration$$>$ satisfying the the usual internal configurations or operations that define a Turing machine that satisfy the consistency condition (the consistency condition is the restriction that any two distinct quadruples must differ at $($$i$$)$ or $($$ii$$)$ but note that the consistency condition must be satisfied by any machine). What does this mean for the internal configuration $\mathfrak o$? That $\mathfrak o$ must be a internal condition (state) of higher 'type' than the ordinary Turing machine states that correspond to the operations of '$1$', '$B$', '$R$', '$L$' ('$1$' prints a 1 on a cell of the tape if the cell is blank, otherwise no change is made on the tape; '$B$' erases the cell if there is a 1 on the cell, otherwise no change is made on the tape; '$R$' moves the device one cell to the right, '$L$' moves the device one cell to the left--note that by the consistency condition, each internal condition and input is uniquely associated with an operation).

As an example, consider the device with internal configurations $q_0$ and $q_1$ whose behavior is determined by $q_0$$1$$B$$q_1$ and $q_1$$B$$R$$q_0$ (this example is found and is quoted almost verabtim by me, from pg 14 of Hartley Rogers $Theory$ $of$ $Recursive$ $Functions$ $and$ $Effective$ $Computability$). (I continue the quote) If such a device is given a tape with a finite run of consecutive 1's and is started in state (internal configuration) $q_0$ on the leftmost cell of the run, it will erase all of the 1's and then stop. If such a device is started on a tape consisting entirely of 1's (i.e. an infinitely long string of 1's on an infinitely long tape), it will never stop. The question now is, can a Turing machine decide whether this simple Turing machine Rogers describes halts or not? A Turing machine should be able to determine, for a finite sequence of 1's that it halts, but how does one code the case where there is an infinite sequence of 1's (I won't consider the case where the tape is completely blank or where there are blank cells before the cells containing 1's since Rogers didn't provide a complete enough description to determine the behavior of the device on those and other inputs)?

So let's consider only the two inputs Rogers considers--the finite sequence of 1's or the infinite sequence of 1's and consider each case: i) the case where it is possible to provide a code for the infinite sequence of 1's and ii) where it is not possible to provide such a code. For case i) even though a Turing machine could (hypothetically) decide whether {$q_0$$1$$B$$q_1$, $q_1$$B$$R$$q_0$} halts or not, one could easily devise a higher-order instruction which would decide, given that the input was an infinite string of 1's, that the device wouldn't halt. For case ii) it is clear that a higher-order instruction would be needed. Indeed, for the halting problem, the machine that would decide whether a Turing machine would halt or not for all inputs would need higher-order instructions for some inputs in order to avoid the self-reference that produces the contradiction which makes the machine (that decides whether a Turing machine for all inputs halts or not), not a Turing machine. Such steps would, for course, be fundamental processes and would qualify for the title, 'oracle'.

This is not a new concept. Goedel, in footnote 48a or his paper " On Formally Undecidable Propositions of Principia Mathematica and Related Systems I" (found in Martin Davis' book $The$ $Undecidable$), says:

"The true reason for the incompleteness which attaches to all formal systems lies, as will be shown in Part II of this paper, in the fact that the formation of higher and higher types can be continued into the transfinite (cf. D, Hilbert, "Uber das Unendliche", Math. Ann. 95, p. 184), while, in every formal system, only countably many are available. Namely, one can show that the undecidable sentences which have been constructed here always become decidible through the adjunction of sufficiently high types (e.g. of the type $\omega$ to the system $P$)."

Also, this:

"It should be expressly noted Theorem XI (and the corresponding results about $M$ and $A$) in no way contradicts Hilbert's formalistic standpoint. For the latter presupposes only the existence of a consistency proof carried out by finitary means, and it is conceivable that there might be finitary proofs which cannot be represented in $P$ (or in $M$ or $A$)." [On pg. 37 of $The$ $Undecidable$]

Thomas Benjamin
  • 6.1k
  • 1
  • 25
  • 39