C and Turing Machines

Question 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:

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".
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.

Question 2

Many years ago people didn't had much to explain ideas and visualize how things will work; in the history of computation there are many "machines", one of the most famous one is the Babbage machine, which explains and clearly shows how to solve simple math problems that weren't simple at all for the machines and the equipment available at that time.

The Turing machine shows how you can start from the building blocks of computation, with an head, a tape, a register and a lookup table and get a working machine, for that time this simple thing was groundbreaking, infact if you just reduce the set of valid states, valid registers, to 0 and 1, you get the basic principles behind modern CPUs.

Tipically the Turing machine + Boolean algebra are a turning point of a good computer science class because they teach you the very basic logic that makes CPU work the way they work.

If you are a programmer you can abstract the essence of a Turing machine to a while construct with an if inside, you can easily guess what the while does and what is the conditional for the if.

On modern CPUs you probably don't even have a while loop, just an endless one, because a CPU simply never sleeps, it always has something to do, even doing nothing means doing something for the CPUs, the IDLE cycle was invented just for that .

Question 3

You could easily implement a very simple algorithm in a Turing machine and find that it took the age of the universe, or much longer, to run. This does not mean that the Turing machine is a bad idea, any more than say a transistor is a bad idea. But to get a useful computing device you may want to to think about running Turing machines (perhaps many Turing machines) in parallel. This is already getting beyond anything that I have seen studied in computing over the last 50 years.

Richard Mullins