Turing machine where the next step is determined by the state and the symbols up to the read/write head

Question

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?

Answer 1

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?

Answer 2

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.