Recursive Functions andTuring Machines - an introduction

Recursive Functions:

Setting: In this section all functions will be of the form where again are the natural numbers.

Definition The following are primitive recursive functions:

The successor function, .
The constant functions, any $\QTR{Large}{c}$
Projections, .
composition: Given primitive recursive functions then
is primitive recursive:
primitive recursion: Given primitive recursive functions and

then the function defined by the following two equations is primitive recursive:

_______________________________________________________________

Example 1:

Example 2 (less formally):

Example 3 (Exercise $\QTR{Large}{n!}$ ):

________________________________________________________________

Definition: The following are partial recursive functions:

Any primative recursive function.
If $\QTR{Large}{g}$ is a partial recursive function such that is defined for all $\QTR{Large}{y<m}$ :

If no such $\QTR{Large}{m}$ exists then is undefined.

A partial recursive function that is defined for all is called (total) recursive.

There are total recursive functions that are not primitive recursive. The Ackermann Function 1 The Ackermann Function 2

___________________________________________________________________________

Notation and Examples:

We write and for $\QTR{Large}{Add}$ and $\QTR{Large}{Mult}$
We write for

The predecessor function:

Note
Truncated Subtraction:
The Equals Function:
(An Aside) The C equals operator:

$\QTR{Large}{eq}$ (
Square Root:

$\QTR{Large}{sqrt}$ ( $\QTR{Large}{x)=}$

Note that $\QTR{Large}{sqrt}$ ( $\QTR{Large}{0)}$ and $\QTR{Large}{sqrt}$ ( $\QTR{Large}{1)}$ are defined.

The Church-Turing Thesis:

Recursive functions are identical to the set of functions that can mechanically computed, that is, are programmable on some deterministic computer.

_________________________________________________________________________

Turing Machines:

Definition :

A Turing Machine $\QTR{Large}{T}$ consists of:

An alphabet $\sum$ : A finite set of symbols including $\square .$
The tape: A 1 dimensional sequence of cells. Each cell is referenced by an Integer.

Each cell can contains a single symbol from the $\sum .$ , all but a finite number of cells contain the blank symbol $\square$ .

At different stages of a Turing Machine computation, the tape will contain a different configuration of symbols.
A finite set of head states $\QTR{Large}{Q}$ .
An Initial state:
A halting state - Accept: .
A halting state - Reject: .
The read/write Head: In a given state $\QTR{Large}{\in Q}$ and "positioned over" a given cell,
A single valued Transition Function: of valid steps.

Read if the head is in state and it is over a cell containing symbol and change the symbol in the present cell to $\QTR{Large}{s_{k}}$ , change the head state to $\QTR{Large}{q_{k}}$ ,

and move $\QTR{Large}{L}$ eft or $\QTR{Large}{R}$ ight one cell, or $\QTR{Large}{N}$ ot at all, depending on $\QTR{Large}{x}$ . It is common practice to write rather than .

Notation: denotes that is in state $\QTR{Large}{q_{i}}$ and the tape contains the consecutive sequence of symbols with all blanks to the left of $\QTR{Large}{s_{1}}$ and to the right of $\QTR{Large}{s_{n}}$ .

Moreover the head is over the cell containing $\QTR{Large}{s_{j}}$ . We call this the state of $\QTR{Large}{T}$ , as opposed to the head state.

Given and valid step we write More generally will be used to denote a sequence of valid steps refered to as a derivation.

__________________________________________________________________________________________

Alternate Definitions: There are many computationally equivalent definitions of Turing Machine..

One A: simple, in fact more commonly used, variation is as above except in the Transition Function, rather than Head , only are available.

To create a computationally equivalent for a given Turing Machine

For $\QTR{Large}{s_{j}}$ each add a new state and rules .
For every step of the form replace it with a step, and for each $\QTR{Large}{s_{j}}$ a rule

Two Another variant defines . Here, in a given step, either the cell under the Head gets rewritten or the Head moves not both.

Exercise (Due ): Show that Two is computationally equivalent to the original definition or to One , hence all three are equivalent.

Three:....An n-tape Turing Machine $\QTR{Large}{T}$ consists of:

n tapes: each as in a single tape machine.
An alphabet $\sum$ : A finite set of symbols including $\square .$ Possibly divided into per tape subsets
A finite set of head states $\QTR{Large}{Q}$ . again as in a single tape machine
n read/write Heads: In a common state but independently positioned over each tape.
A single valued Transition Function: of valid steps.

______________________________________________________________________

The Subtract 1 Turing Machine:

The Transition Function:
- , there are no negative numbers so " $\QTR{Large}{0-1=0}$ " .

Exercise (Due May 2 ): Build a Turing Machine that interchanges the position of two strings of $\QTR{Large}{1}$ s and $\QTR{Large}{0}$ s that a separated by a single blank and with the tape blank elsewhere.

That is, starting with a tape that contains with the Head positioned over the cell containing the initial $\QTR{Large}{x}$ , halts when the tape contains

with the Head positioned over the cell containing the initial $\QTR{Large}{y}$ .

Hints:

One way to approach this problem is in terms of the Exercise just below, Build the two TMs and combine them.

A little care has to be taken because one of the two strings may be empty (or both, the tape could be blank)

The number of.states or symbols you use for the TM or TMs is not restricted. An symbol marking where the strings start or end might be useful.
For those of you who are building your first TM, It might be useful to build the machines assuming the $\QTR{Large}{x}$ s are $\QTR{Large}{1\ }$ s and the $\QTR{Large}{y}$ s are $\QTR{Large}{0}$ s and then modify the result for the other case.
Building a TM is like writing any program, starting with an activity diagram or flow chart is usually a good idea.

________________________________________________________________________________________________________

Theorem(Informal):

One can show that the set of Partial Recursive Functions is identical to the set of Turing Machines computable functions.
Total Recursive Function correspond to Turing Machine computable functions that always halt.
One can enumerate the Valid Turing Machines (A program syntax checker)

_________________________________________________________________________________________________________

Universal Turing Machines:

An Intel Corporation Almost Universal Turing Machine

Theorem(Informal):

One can develop a Turing Machine Description Language (TMDL). (Read "programming language").
Given a (TMDL) one can build a Universal Turing Machine $\QTR{Large}{U}$ such that:
- , If $\QTR{Large}{M}$ is a Turing Machine and $\QTR{Large}{<M>}$ is a Turing Machine Description of $\QTR{Large}{M}$ .
- $\QTR{Large}{x}$ is a string that $\QTR{Large}{M}$ accepts then:

Technicalities:

There is no restriction, $\sum \$ and $\QTR{Large}{Q}$ on any particular $\QTR{Large}{M\ }$ except that they are finite sets.
$\QTR{Large}{U\ }$ has specific, finite $\sum \$ and $\QTR{Large}{Q}$ .

The first step in the proof of this Theorem would be developing a general alphabet encoding that could be used to encode the alphabet of any Turing Machine.

would have to be understood in terms of that encoding.

______________________________________________________________

A Convenient 3-tape Turing Machine :

The input tape: A read-only tape containing the input, unidirectional in that its head can only move left to right;
The work tape: Where all computations are carried out, bidirectional but initially blank:
The output tape: unidirectional and Initially blank, where the result of the computation is copied from the working tape, before halting.

We say such a Turing Machine halts on input $\QTR{Large}{p}$ with output $\QTR{Large}{x}$ , and write if $\QTR{Large}{p}$ is to the left of the input head and $\QTR{Large}{x}$ is to the left of the output head after $\QTR{Large}{T}$ halts. .

____________________________________________________________________________________________________________________

Exercise (Due May 2 ): (Informal, again Kolmogorov Complexity ) Given Turing Machines and , and descriptions , . $\QTR{Large}{>}$ realizing functions what would a description for a Turing Machine realizing look like. You answer should, again informally, list a series of general steps creating the description from any and . $\QTR{Large}{>,}$ (Hint: How would you do this using Java, or C, or javascript)

______________________________________________________________

A Prefix Universal Turing Machine:

Yet another 3-tape variant, important for Kolmogorov Complexity, has

, no blank, with the work tape initally all $\QTR{Large}{0}$ 's
The set of $\QTR{Large}{p}$ on which $\QTR{Large}{T}$ halts forms a prefix code. Such codes $\QTR{Large}{p}$ are called self-delimiting programs.
In creating a description of a Turing Machine, the halting states are replaced by some appropriate "copy to output tape" subroutine.

Note: Getting from A Convenient 3-tape UniversalTuring Machine to A Prefix Universal Turing Machine is not a huge step (see the encodings below)

___________________________________________________________________________________

"Standard" notation:For a string $\QTR{Large}{x}$ ,

A simple prefix encoding:

For any string in , define to be $\QTR{Large}{n\ 1}$ s followed by a $\QTR{Large}{0}$ .followed by $\QTR{Large}{x}$ .

, $\QTR{Large}{.}$ (

The map is a prefix encoding of . and

The "standard" prefix encoding

Let $\QTR{Large}{b}$ ( $\QTR{Large}{x)}$ be the following binary string ordering function

$\QTR{Large}{b}$ ((((((

For any string in , $\QTR{Large}{\ }$ define to be the prefix encoding above, of

s followed by a $\QTR{Large}{0}$ followed by .

. ,where the least integer

Finally let , concatinating $\QTR{Large}{c(x)}$ and $\QTR{Large}{x.}$

The map is a prefix encoding of .called the standard prefix encoding.

. $\QTR{Large}{\ }$ where, again , , a significant improvement. as $\QTR{Large}{n}$ becomes large

psudo code to decode

$\QTR{Large}{m=}$ Count $\QTR{Large}{1}$ s up to but not including first $\QTR{Large}{0}$ , The next $\QTR{Large}{m}$ string characters, after the $\QTR{Large}{0}$ is the binary representation of the length of $\QTR{Large}{x\ }$ , call this .
$\QTR{Large}{x=}$ next $\QTR{Large}{n}$ string binary digits after the first $\QTR{Large}{2m+1}$
The next string begins after the first