Disclaimer: I'm a software engineer with only an undergrad education and have never published or anything so please forgive any minor notation or jargon blunders - but of course feel free to point them out because I want to learn.

When I was in school for CS undergrad one of my professors explained that there are more languages than Turing machines. This irked me (Are there questions (languages) than answers (algorithms) in the world?) until I realized that Turing machines can be generalized to fix this discrepancy so that all Languages have a corresponding machine:

Suppose I have some language $L$ that has no corresponding Turing machine.

I will define a Unit Turing Machine ($UTM$) to be a Turing machine that accepts only 1 string and rejects all others. So the language of $UTM_0$ is $\{0\}$, $UTM_1$ is $\{1\}$, $UTM_2$ is $\{10\}$, etc. There's a $UTM$ for each non-negative integer that corresponds to the binary representation of that integer as the single string it accepts.

Note that $L$ is a language so it is a subset of all finite-length binary strings, so $L$ can be enumerated (although if it were finite it would have a Turing machine, so it's countably infinite).

So let's say we had some enumeration of $L=\{l_0,l_1,l_2,...\}$.

Let's say I map elements in $L$ to their corresponding $UTM$ so that I now have a set of $UTM$ and call it myTuringMachineList. Since $L$ is countable, so is the mapped myTuringMachineList.

Now I can perform the following pseudocode algorithm on myTuringMachineList to decide input string input:

function computeTheUncomputable(myTuringMachineList, input)
    found := false;
    i := 0;
    while not found
       j := 0;
       while not found and j <= i
           // executes the jth myTuringMachineList Turing machine 
           // through i steps with input input.
           result := execute(myTuringMachineList[j], input, i);
           if result = accepted // could also be rejected or undecided
              found := true;

I think this approach is called dovetailing. Every string in the "un-acceptable" language $L$ will now be accepted in a finite amount of steps through this algorithm, which I think can execute any countable finite set of Turing machines in parallel.

While this algorithm seems like it would be a Turing machine itself, it relies on having access to this infinite list of Turing machines (and a way to execute them as a black box), which effectively allowed me to construct a more powerful Turing-like machine that has an infinite number of states and transition rules... By breaking out of finite-ness to my states and transition rules I gained something useful: languages I could not otherwise accept in a finite amount of steps. Although this implementation suffers from the inability to reject in a finite number of steps.

My question is: Is there a name for a useful Turing-like machine (such as the one described above) that is more powerful than a Turing machine? Alternatively, if has someone already given this proof (or an analogy or more generalized version) then that reading that would probably tell me what they called their machine and answer my question.

  • $\begingroup$ I did some more googling: I think this idea might be somewhat related to Oracles. You could maybe look at the computeTheUncomputable function as an Oracle if it were called by someone else in the context of being a "black box"; I'm just giving it a construction/implmentation so that it's not a "black box", so it's not quite an Oracle since it has bit more structure (from my understanding of an Oracle). $\endgroup$ Apr 12, 2016 at 15:42
  • $\begingroup$ The "Oracle-ness" (beyond Turing machine capabilities) of it comes from the infinite myTuringMachineList because that's the part that's cannot be captured by a Turing machine (and I just "magically" chose ahead of time the "correct" Unit Turing Machines to include). $\endgroup$ Apr 12, 2016 at 15:42
  • 3
    $\begingroup$ Congratulations, you invented (a particular case of) oracle machines. $\endgroup$ Apr 12, 2016 at 16:47
  • 1
    $\begingroup$ What do you mean by "useful"? We're not currently aware of any actual, physically buildable computer that's more powerful than a Turing machine and the so-called "physical Church-Turing thesis" hypothesizes that no such machine can be built. So, if your notion of "useful" includes having the possibility of physical existence, the answer is "apparently not." $\endgroup$ Apr 12, 2016 at 20:06
  • 3
    $\begingroup$ A trivial change to your machine makes things decidable. Just keep two lists of finite approximations of languages: one for the language and one for its completement. Then search both in parallel. As I said, you invented a variant of oracle machines. You are not doing anything new. $\endgroup$ Apr 12, 2016 at 22:37


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.