Given a modified type of turning machine where

$\delta = Q\times \Gamma^* \implies Q\times \Gamma \times \{L,R\}$

where the next step of the machine is determined by the current state and whatever written on the tape up to the current point.

For example: if the tape content is $a\_ab\_\$\$a$, and the head is on the left \$, then the next step is determined by the state and the word $a\_ab\_\$$.

  1. How can I prove that unrecognized languages can be recognized with these types of machines?
  2. Do those machines contradict the Church–Turing thesis?
  • $\begingroup$ Just to note that the states can be removed from this kind of machine without diminishing their collective power since the machine can just treat some symbol as states, writing them on the tape. $\endgroup$ – John L. Jul 7 '19 at 23:56
  • $\begingroup$ @Apass.Jack I'm not sure I understand what you meant with your second comment. This is a question from my text book and this is how it's defined. And by "this subject" I meant Turing machines different variations. Perhaps it was expressed badly so I took it off, sorry. $\endgroup$ – user99674 Jul 8 '19 at 1:18
  • $\begingroup$ Could you please add a reference to the textbook in which this problem appears? Thanks. $\endgroup$ – John L. Jul 8 '19 at 10:16
  • $\begingroup$ Sorry for not responding erlier, it is actually taken from a small textbook my teacher handed which is not in english $\endgroup$ – user99674 Jul 8 '19 at 11:01
  • $\begingroup$ OK, although it would be great to credit that "small textbook". $\endgroup$ – John L. Jul 8 '19 at 11:06

Suppose we are given a language $L$ of words of finite length. We will construct machine $M_L$ that runs as the following.

$M_L$ starts at state $q_0$. On input $x$ of finite length that is put to the right of its head, $M_L$ will move right all the way to the end of input, keeping the input and state intact. (This might mean nothing if the input is empty.) When $M_L$ read the first blank symbol, what is written on the tape up to the current point exclusive is exactly the input $x$. (If current point should be included, let $M_L$ go back a cell.) It halts, changing state to

  • $q_1$, an accepting state if $x\in L$,
  • or $q_2$, a rejecting state otherwise.

It is clear that $M_L$ decides $L$.

Well, it is reasonable to say that that $M_L$ does not compute $L$ at all. $M_L$ just knows effectively each and every word in $L$ without any computation. When $L$ is infinite or even undecidable, we are not able to build or truly simulate such a machine within any bounded time by any known physical means and intelligence. Hence, we would not believe those imaginary machines contradict the Church–Turing thesis.

Exercise. Given a modified type of turning machine where

$$\delta: Q\times \Gamma^* \to Q\times \Gamma \times \{L,R\}$$

where the next step of the machine is determined by the current state and the content of last $\lceil\log_2n\rceil$ cells that has been read by it, where $n$ is the number of steps the machine has run. Can some unrecognized languages be recognized with these types of machine?

  • $\begingroup$ When L is infinite we get infinte $Q, \delta$ and therefore can't build such a machine. Why does this machine work for unrecognized languages and doesn't work for undecideable languages though? $\endgroup$ – user99674 Jul 8 '19 at 8:26
  • $\begingroup$ Exercise: I can tell that $\delta$ would also be infinite now so such a TM would also not contradict Church-Turning thesis with its calculating power becuase we don't know how to build such a machine in a reasonable time. implementation: $M$ starts at $q_0$. on input $x$ of finite length that is put to the right of its head, $M$ will read the entire input and stay in $q_0$, after that it'll make a pesuedo $2^{|x|}$ moves. Then change state to $q_1$, an accpeting state if the last $[\log_2n] = |x|$ cells that were read are in $L$, otherwise $q_2$, a rejecting state. Is that a good direction? $\endgroup$ – user99674 Jul 8 '19 at 8:29
  • $\begingroup$ This machine works for any unregcognized languages, including undecidable languages. Note that words are usually assumed to be finite length. I was just being extra clearer in writing " of words of finite length". $\endgroup$ – John L. Jul 8 '19 at 10:15
  • $\begingroup$ Yes, you have done the exercise correctly. It could have been slightly better if "$2^{|x|}$ moves" could have been "$2^{|x|}-|x|$ moves". $\endgroup$ – John L. Jul 8 '19 at 10:19
  • $\begingroup$ It might have been less confusing had I written "$M_L$ halts in all cases. The language $M_L$ acceptes is $L$." instead of "$M_L$ decides $L$". $\endgroup$ – John L. Jul 8 '19 at 11:02

Here is an informal argument. I will leave you to fill in the gaps.

If such an enhanced Turing machine (let's call it a megaTuring machine) were possible, then you could program it to accept any language (any subset of $\Gamma^*$) simply by listing the words in the language. Even a language for which a formal grammar does not exist (i.e. an unrecognizeable language) could be "recognized" by a megaTuring machine programmed with a list of the words in that language.

The problem is that the set $\Gamma^*$ is infinite, so in general the program for a megaTuring machine is infinitely large. We could reduce the program to a finite size if there were some rule that allows us to compress $Q \times \Gamma^*$ to a finite size (for example "do $X$ if tape content is $a$; do $Y$ if tape content is anything else"). But these are precisely the cases where the language recognized by the megaTuring machine can be described by a formal grammar, and so the behavior of the megaTuring machine can be reproduced by an ordinary Turing machine.

Since part of our informal definition of an algorithm is that it can be described in a finite amount of space and time, the programs that a megaTuring machine could run are not, in the general case, algorithms. So the concept of a megaTuring machine does not contradict the Church-Turing thesis.


Your Answer

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