Turing Machines

the automaton used to describe both type 1 (context sensitive) and type 0 (unrestricted) grammars

Reminder:  CSG:  The left side of a production rule contains at least one nonterminal.  The right side is no shorter than the left side.  (Since this prevents the empty string from ever being generated, sometimes its tweaked to allow the empty string.)

Unrestricted grammar:  The left side of a production rule contains at least one nonterminal.

CSG's are decidable.  Given a grammar and a string, you can always tell yes or no for sure whether that grammar generates that string.

Unrestricted grammars are not necessarily decidable.  A Turing Machine can be programmed to Halt on a valid string and not halt on an invalid string, and that's the best you can do.  If you want to see whether a string is generated by an unrestricted grammar, just set 'er goin', and wait.  If it takes a long time, maybe that's because the string isn't accepted, or maybe it's because it's just taking a while; hey, try waiting a little longer.

A Turing Machine (there are different but equivalent definitions):

You have a set of states, one of which is called the start state, and one of which is called the halt state.

You have an alphabet, the set of characters used by the language of the TM.

You also have a tape alphabet which is a superset of the language alphabet.

You have a transition function that takes a state and a tape character and returns a new state (or halt) and returns a new tape character OR "left" OR "right".

You imagine that the tape is infinite in both directions, you can move left or right on the tape as much as you like, you can read characters, and write characters anywhere on the tape but only at the position of the head.

The input string is written on the tape before you start.  Again, the exact format of this depends on the definition.

My definition:  the string on the tape has to adhere to a "prefix code".  What this means that no valid input is the first part of another valid input.

For example, if "ABCD" is valid input, then I am asserting that "A" "AB" "ABC" and the empty string are not valid input.

I personally called it the "Elektra Woman And Dyna Girl" code.

The classic "prefix code" used by most sane people is to follow each input string with a space, and forbid space from the language alphabet.

The reason I like a more general description of knowing where the string ends is that sometimes I like my turing machine to have more than one argument.

arg1 <space> arg2 <space> arg3 <space>

And my prefix code would know that I was done parsing when I hit the third space.

Or, suppose I want to write a Turing Machine with a varying number of arguments

arg1 <space> arg2 <space> arg3 <space> arg4 <space><space>

And my "prefix code" would say that the input is done when I hit the second consecutive space.

Other than the input, what's on the tape when the program begins?  A lot of definitions say that everything is blank other than the input.  I usually say that the squares on the tape (other than the input) are undefined at the beginning of the program.

The Halting Problem, perhaps the most famous of the "undecidable" problems.

Given a program, and an input to that program, determine YES or NO whether that program halts on that input.

Assume that this program exists, I call it H, and H takes two arguments:  P, a program, and I, input to that program.

So, *I* am going to write my own program G (P):

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

Run G on itself:  G(G):  Does this halt?

Well, let's say it does halt, then H (G,G) is true.  But that means my G program goes into that while(1) infinite loop, so G(G) doesn't halt after all.

So, let's it doesn't halt, then H(G,G) is false, so that if statement in G(G) doesn't fire the loop and the program ends quickly, so I guess G(G) does halt.

This is a contradiction, and our assumption is wrong, there is no program that determines for sure YES or NO whether a certain program halts on a certain input.  (However, we can always work to improve the software we have; over time, we may discover other classes of problems that we can decide, but we'll never get the whole thing.)

Church's Thesis / Church-Turing Thesis:  No physical machine that can be built in reality can ever solve a class of problems that a Turing Machine cannot solve.

Original Turing Machine did NOT come with a two-way infinite tape.  It came with a one-way infinite tape, and if the head fell off the left end, that was called a "hang" and you can think of that as a permanent non-halting situation.  It turns out that is equally powerful to a Turing machines we define today.