1
$\begingroup$

In Arora-Barak, the authors mention a way how TMs can compute everything that can be computed by computers. The idea is that every high-level language program has an equivalent machine language program which is basically a sequence of instructions. These instructions are easy enough to be implemented in TMs. I am attaching the whole argument in a snapshot. What I am not able to get is that how can TM determine which instruction it has to execute? Of course, we cannot write the complete sequence of instructions in states because number of states is fixed but length of the program may be not.

The complete proof in Arora Barak

Improve this question
$\endgroup$

2 Answers 2

Reset to default
1
$\begingroup$

The tape of the TM stores the code of the program (the sequence of machine instructions), followed by the memory of the program. You design a TM that traverses back and forth between the code section (to find the next instruction to execute) and the memory section (to execute that one instruction and update memory appropriately), repeating until it has finished simulating execution of the program..

Improve this answer
$\endgroup$
1
$\begingroup$

They aren't trying to show that there is a single Turing machine that can run every C program (although that's also true). They're trying to show that for every C program, there is some Turing machine equivalent to it. Every C program compiles to a fixed finite number of machine instructions, so you can encode them as states of the Turing machine and end up with a fixed finite number of states.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.