UNIVERSAL TURING MACHINE

Design a Turing Machine that can emulate ALL Turing Machines.

In other words, can you encode all Turing Machines in a consistent fashion, so that you can load up a Turing Machine encoding on a tape and then have this Turing Machine read that encoding and give the answer that the encoded would have given on a specific input.

Yes, of course you can.

We have to encode each state:  Each state has a list of characters each character is associated with a command (L, R, or write a character) and a new state (which is either one of the states in the set or HALT).

We have to encode the "tape within a tape".  The head position on the simulated tape. (You might use a left and right marker to denote the beginning and end of the simulated tape.

Interpret state 1 as being the start state.  State 0 as being the HALT state.

Each state consists of character command <new state>, maybe put spaces between states, after the last state have some sort of delimiters for {initial tape value} (input to the emulated Turing Machines.

So, how can we emulate operating this Turing Machine

How do we add to the tape on the right?  On the left?

How do we jump to another state?  How do we find that state in the list of states?

How do we keep track of the tape head?

Tape Head:  have another character represent head:

{LAHSAGNA}  Interpret the tape string as "LASAGNA" with the head on the S.  Moving left and moving right involve swapping characters.  Moving off the end of the tape is easy, you have move the } one space to the right and that gives you more room.

Moving off the left end takes a little more work.  You will shift everything down one space to right.  Move to the } move that to the right, keep moving characters one space to the right until you reach the {.

Anytime a state tells you to make a change to the tape.  Put a marker where you are.  Move right until you get to the {, make your change, then go back left to the marker.

Now, how do you jump to the new state, understanding that you can't store state numbers in the finite control?

Now think of state id's has decimal integers, 1 is the start, 0 is the halt.  You can copy the state number you're looking at to the left end of the tape.  One character a time, mark your position, store the digit in the finite control, move to the left of the tape, write that digit, move right back to the marker, and so forth.

Now, that I have the state number on the left of the tape.  I go through the states one by one.  When I hit a state, I mark it.  Then go back to the left end of the tape and subtract 1.  Then go right to the marker, unmark it, move right to the next state, mark that, and then back to the far left to subtract 1.  I will eventually get to zero, and my marker is on the state I want.

****

Halting Problem:

I have a program (or a TM) and the input that this program will be running on?  Can I write a program (or design a TM) that will say YES or NO definitively whether that program halts on that input?

Assume Halt (P,X) exists.  I just wrote it.  It returns true if P halts on X, false if it does not.

So, I will will write the program G(P):

if (HALT (P,P)) while (1);

Will G(G) halt?  If it does then HALT(G,G) is certainly true.  Therefore line 49 goes into an infinite loop and G(G) does not halt.

If G(G) does not halt, then HALT(G,G) is false, so line 49 will skip the infinite loop, and G(G) halts.

CONTRADICTION.  My assumption is false, and Halt (P,X) does not exist.

REDUCING TO THE HALTING PROBLEM.

To prove that a certain problem is unsolvable, you "reduce it to the Halting Problem".  This means, that you assume the problem and solvable, and using that problem, show that you can now write a program that definitively determines whether an arbitrary program will halt on arbitrary input.

ALWAYSHALT (P):

Returns YES if P always halts no matter what input you give it.
Returns NO if there is an input somewhere that will cause P not to halt.

Prove that this cannot be done.  This program does not exist.

Write a program P'.  P' ignores its own input and simply emulates P running on X.  (For some input X).

Since P' doesn't even examine its own input, it always the same thing no matter what the input is.  So, with ALWAYSHALT, I can determine whether P' always halts.  If it does always halt, then P must halt on input X.  If it does not always halt, then P can't halt on input X.

So, I have a slick way to write HALT (P,X).  Therefore ALWAYSHALT can't possibly exist.

A slick new IDE has a feature that it can use red squigglies to mark unreachable lines of code.  So with this feature, you can then remove code that you know will never be hit.  Prove that this feature cannot possibly always work.

(Assume that you know that NEVERHALT also can't possibly exist.)

Well, take the code you want to test, and an extra last line.  Just before the program ends, put some line in the code; it doesn't really matter at.  If the IDE flags that line as unreachable, then the original program must never halt.  If it isn't flagged, then there's some input somewhere that will cause the original program to halt.