3
$\begingroup$

The machine can only write on the input word, not in empty cells. Prove that such modified Turing Machine is not equivalent to regular Turing Machine.

From my point of view, we should base on fact that number of configurations of this machine is finite, because input word (so different states of tape), alphabet, number of states are finite.

Lets suppose that this machine is equivalent to regular machine.
Here, we use following fact:

(*) Machine that rejects immediately if it visits the same configuration twice is equivalent to regular Turing Machine.

So, lets come back to our task: We assumed that this machine is equivalent so it is able to simulate some Turing machine. Lets simulate any Turing machine on this and we have a guaranty that this simulation is finite, because we use (*) and fact that number of states is finite. Hence we got contradiction because halt problem is undecidable.

What do you think about my solution ?

Edit
Using Hint's of answerer I try again:
I can use space hierarchy theorem. So, Lets suppose that such machine is equivalent to regular Turing Machine. Hence, each decidable problem can be solved in linear space. $n^2$ is construable and $n\in O(n^2)$ so using space hierarchy theorem we conclude that there exists problem in class $DSPAC(n^2)$ which doesnt belgons to $DSPACE(n)$. It is contradiction, so we proved our thesis.

Second way:
I think that my solution works. Each Modified Turing Machine either finish and reject/accept or get to the same state. Because we know that machine which reject always after enering to the same state is equivalent to regular Turing Machine. So our modified machine is able to decide Halt Problem.

$\endgroup$
  • $\begingroup$ I recommend you find a simple function that cannot be implemented by your modified Turing Machine. $\endgroup$ – David G. Stork Mar 24 '17 at 21:38
  • $\begingroup$ Can you show me such function ? Also try to check me reasoning, please $\endgroup$ – user343207 Mar 24 '17 at 21:39
2
$\begingroup$

Your modified machine is not quite finite, because it gets to use more space when the input is longer.

In other words, you're being asked to prove that there are decidable problems that are not in LINSPACE.

Assuming that you don't have an appropriate space hierarchy theorem available (which would make this conclusion immediate):

Your modified machine cannot possibly run for more than $nk\cdot|\Sigma|^n$ steps without hitting a repeated global state (and thence cycle endlessly). Use the time hierarchy theorem to construct a problem that cannot be decided within any time limit of this form.

$\endgroup$
  • $\begingroup$ I edited my question and add some solution (two approaches). Can you look again and check it ? Moreover, can you show solution with time hierarchy theorem ? $\endgroup$ – user343207 Mar 25 '17 at 12:45
0
$\begingroup$

This is essentially what is known as a Linear Bounded Automaton, or LBA.

It is easy to see that the language accepted by an LBA is recursive: For a given input, there are only a finite number of configurations (tape contents, head position), so you can check all possible computations (a finite number, as each has finite length!) and check if any one accepts. On the other hand, a Turing machine can accept a non-recursive language. Thus Turing machines are strictly more powerful.

$\endgroup$

Your Answer

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