C and Turing Machines

Question

I have learned that Turing Machine is good to use because it has the "same power" as out computers.
Also,my lecture said that every C code can be executed by some Turing Machine. I believe that is the key for leaning this subject, but i didn't found any proof for that.

What is the algorithm to translate a C code to some Turing machine which execute it and gives the same output for as the c code will give for some input?

Answer 1

An algorithm that converts (arbitrary) C code into a turing table would be quite difficult to write, and I think that it would not be very instructive. I would rather suggest to consider the following:

1. To execute a C program, it has to be compiled to machine code. This code is something your CPU can understand: the machine code tells the CPU what to do. This can be for example "Read a number from a certain location in memory, read another number from another location in memory, add both numbers, store the result in yet another location in memory". This would be approximately what the C compiler creates from a = b + c;. The CPU can only do "simple things" such as arithmetic, access memory, and jumps to different locations in the program. The last bit is used to implement loops and if-then-else constructs: "If some condition is true, jump to this location and execute the code there, otherwise, jump to another location".
2. A Turing Machine also can do arithmetic: Assume we have two numbers stored on the tape in unary representation, e.g. to calculate 4+5, our tape would look like #@||||#|||||# (# are blank parts of the tape, @ is the head), To add the numbers, our machine just needs to remove the inner #, replace it by | and remove one | from either start or end of the tape to get #@|||||||||#. With the turing instruction table, you are able to make decisions depending on the current state of the tape: If we are in state A and see a |, do this (write a symbol, move head, change state), else, do something else.

So my suggestion is that you don't try to get from C to a turing machine, but to imagine/look up/ask what a real world CPU has to do to execute a certain C statement, and then figure out that a Turing machine can do the same thing.

Yet another approach: A real world computer that executes compiled C programs consists of

• a CPU that "does things"
• memory that "stores things"
• a program to "coordinate things"

A Turing machine consists of

• a head that can read and write on the tape == do things
• an (infinite! even bettern than a PC!) tape == store things
• an instruction table == coordinate things

I hope this helps.