Computation Theory

What is an algorithm?

Turing proved that both his Turing machines and Lambda's calculus were computationally equivalent.

-Expand this from Wiki

 

The Halting Problem

This is the decision problem with S=set of all pairs (A,D) where A is an algorithm and D is a datum on which it is designed to operate, P= "when A is applied to D it eventually halts".

Sketch of the proof:

H(A,D)= { 1 if A(D) halts, 0 if A(D) otherwise/doesn't halt }

If there was such an algorithm H, we could define an algorithm C:

C(A)= { Halt if H(A,A) is 0/Loops, Loop if H(A,A) is 1/Halt }

By setting A=C we derive a contradiction:

C(C) will halt if H(C,C) loops ie if C(C) loops.

C(C) will loop if H(C,C) halts ie if C(C) halts.

 

The final step in the proof of the undecidability of Hilberts Decision Problem was to construct an algorithm to encode instances A(D) as arithmetic statements: so if the arithmetic statement was provable then A(D) halted.

 

Diophantene Equations

"Given an algorithm which, when started with any Diophantine equation, determines in a finite number of steps whether there are natural numbers satisfying the equation."

This was later shown to be equivalent to the halting problem, and hence unsolvable.

 

Notation

A partial function from a set X to a set Y is specified by any subset f ⊆ X x Y satisfying (x,y) ε f & (x,y') ⊆ f => y=y'

f(x)=y means (x,y)ε f

f(x)ê means there is some y such that (x,y)ε f

f(x)é means there is no y such that (x,y)ε f

Pfn(X,Y)= set of all partial functions from X to Y

Fun(X,Y)= set of all total functions from X to Y

Register Machines

Elementary Operations

·        Add 1 to a natural number

·        Test whether a natural number is 0

·        Subtract 1 from a positive natural number

·        Jump

·        Conditional (If-then-else)

 

Components

Finitely many registers R0,...,Rn

A program consisting of a finite list of instructions of the form

Label: body of instruction

Instructions labelled sequentially from 0.

There are three instructions:

L: R+ -> L' Add 1 to contents of register R and jump to instruction labelled L'

• L: R- -> L', L'' If contents of R is > 0, subtract 1 from it and jump to L', otherwise jump to L''
• 

L: HALT

 

 

A computation either continues forever, obeys a HALT, or jumps to a non-existant label (erroneous halt).

 

The relation between initial and final register content defined by a register machine is a partial function.

 

A partial function f(x)=y is register machine computable if a register M can start with x in Rin and 0 in all other registers halts with Rout containing y.

f(x0,...,xn)=y is register machine computable iff there is a register machine M with at least n registers R0,...,Rn if starting with x0-xn in R0-Rn the machine halts with R0 containing y.

 

Coding Register as Numbers

A key part of the Turing/Chruch solution of Hilberts decision problem was the ability to describe algorithms as numbers.

 

Pairs

í x,y î = 2^x.(2y+1)= |y in binary|1|x 0's|

< x,y > = 2^x.(2y+1)-1=|y in binary|0|x 1's| (So you can have 0)

 

Eg;

í 0,0 î = 2⁰(0+1)=1

 

Lists

N* = set of finite lists = {} U N U ... U Nⁿ (lists of length N) U ...

You can apply cons, head and tail to a list.

[nil]=0

Cons(x,l)= í x,l î = 2^x.(2l+1)

Thus [x1,...,xn]= íx1, íx2,... íxn,0î .. î î

[x1,...,xn]= |1| xn 0's| 1|xn-1 0's| ... | 1 | x1 0's|

 

Eg;

[2,1,3] = 100010100

Note the reversal of order when reading in binary.

 

Coding Programs

The (i+1)th instruction in the program listing is labelled Li.

 

If a program Prog is

L0: body0

L1: body1

...

Lm: bodym

 

Then [Prog] = [cody(body0),...,code(bodym)]

Where:

code(R+ -> Lj) = í 2i,j î

code(Ri- -> Lj, Lk) = í 2i+1, <j,k> î

code(HALT) = 0

 

 

Decoding a program

Any natural number decodes uniquely as a program: first decode as a list [x1,...,xn] and then decode each xi as an instruction:

• If x =0 then the instruction is HALT
• Else decode x as a pair í y,z î and
  • If y is even then instruction is

Ri+ -> Lj where i=y/2 & j=z

•  
  • Else (y is odd and) decode Z as a pair Z=<u,v> and the instruction is

Ri- -> Lj, Lk where I = (y-1)/2, j=u & k=v

 

Example:

666 = 1010011010 = [1,1,0,1,1]

0= HALT

1= í 0,0 î (as 2⁰(0+1) ), y=0 & z=0, y is even, i=0/2 & j=z=0, R0+ -> L0

2= í 1,0 î = í 1, <0,0> î, R0- -> L0,L0

 

So the program is

L0: R0+ -> L0

L1: R0+ -> L0

L2: HALT

L3: R0- -> L0,L0

L4: R0+ -> L0

 

Universal Register Machine

U has registers P(rogram), A(rgument).

Loading P with e (The index of a program) and A with a (the value of the registers), U will decode e as a program and run it with a as a list of register values and carry out the computation.

 

U will:

1 Copy P to T, and the PCth (currently executing) item in T to N

2 Decode N

3 Remove register values in A up to one required, putting in R and saving preceding values in S

4 Execute instruction on value in R, update PC, restore register values from R and S to A, loop to 1

 

The registers of U

P- Code of register machine to be simulated

A- Current contents of registers of the register machine being simulated

PC- Program counter - holds the number of the current instruction

N- Holds the code of the current instruction

C- Indicates the type of the current instruction

R- Holds the contents of simulated machines register that is to be incremented/decremented by current instruction

T- Holds a working copy of the program code

S,Z- Auxilarry registers for intermediate computations

 

The Halting Problem, in terms of register machines

A register machine H decides the Halting Problem if, loading R1 with e and R2 with [a1,...,an], the computation of H halts with R0 containing either 0 or 1;

R0 contains 1 at halting iff the computation of the program e with registers set to [a1,...,an] does halt.

 

Let C be obtained from H by replacing START by

(where Z is a register not mentioned in H's program)

Ie So when you start C with R1=C you also set the registers (a1,...,an in R2) to be C.

 

And also by replacing all HALTs (and jumps to a label with no instruction) with:

 

 

Ie So C halts when H halts with R0=0 ie if the computation of e loops forever.

 

 

So:

C started with R1=C eventually halts iff

H started with R1=C halts with R0=0 iff

Progc started with R1=C does not halt iff

C started with R1=C does not halt

Contradiction.

 

 

Undecidable Sets of Numbers

A subset S of N is register machine decidable iff there is a register machine M with the property that when started with R1= x always halts with R0 containing 0 or 1; moreover R0=1 iff x is an element of S.

S is called undecidable if no such M exists. Ie if you can't work out if something is a member of S then S isn't decidable.

 

For example:

S1 = {<e,a> | фe(a)! }

Ie A one argument version of the Halting Problem

 

S ⊆ N is decidable iff the characteristic function of S

Xs(X)={ 1 if x є S, 0 if x ! є S

is computable. Such subsets are also called recursive.

Informal Definition of a Turing Machine

The machine starts with the tape head pointing to

Computes in discrete steps, the result of which depends only on current state and symbol at tape head position

Possible actions are:

• Overwrite current tape cell with a symbol
• Move left, right, or stay stationary
• Change to another state

 

 

 

Formal Definition

• A finite set Σ of tape symbols containing (first symbol) and (blank symbol)
• A finite set K of machine states containing a special element S= initial state
• The transition function ð є Fun (K x Σ, K U {acc,rej} x Σ x {L,R,S})

 

ð(q,a) = (q',a',D)

q=current state, a=current tape symbol, q'=next state,a'=next symbol,D=direction

·        If q' = acc the machine has reached an accepting state (it overwrites a with a' then halts)

·        If q' = rej the machine has reached a rejecting state (it overwrites a with a' then halts)

·        If q' є K the machine:

o       Overwrites a with a'

o       Changes to state q'

§         Moves one cell Left if D=L

§         Moves one cell Right if D=R

§         Stays stationary if D=S

 

A Turing machine can be specified by (q,l,r)

q: Current state є K U {acc, rej}

l: Finite non-nil list of elements of Σ starting with the current symbol, reading to the left, and ending with

r: Finite, possibly nil, list of elements to the right of the current symbol

 

The transition relation holds iff the order of l and r are preserved.

 

Example Turing Machine Computation

If a Turing machine is in state q and reads the value 0 and the relevant part of the transition function is:

	0
q	(q',1,R)
q'	(rej,1,S)

It would overwrite the 0 with a 1, go into state q' and move to the right. Say the character on the right was also a 0, the Turing machine would write a 1 and halt in a rejecting state.

Turing machines can be implemented by register machines

• Number all states (including acc,rej,S) and all tape symbols (including and )
• Use the coding of lists to code Turing machine configurations (q,l,r) as numbers [q,[l],[r]]
• Use registers S(tate), T(ape symbol), D(irection, L=0 R=1 S=2 say)

ð(S,T) = (S,T,D)

• Use registers C to hold codes of Turing machine configurations
• L to hold codes of current tape symbol and all to the left
• R to hold codes of all the tape symbols to the right

 

The register machine halts iff the Turing machine halts and in that case C holds the code of the final configuration.

 

(Copy image from p73)

 

Register machines can be implemented by Turing machines

• To code lists on a Turing machine tape:
  • Represent a number x by x 1's. Eg; 3=111
  • Mark the beginning and end of a list with 0
  • separates numbers on the list

01111110 = (3,2,1)

The tape will look like:

• 0111 111110... = (3,4,1)

 

 

A partial function is Turing computable iff it is register machine computable.

 

 

Church-Turing Thesis

"Every algorithm (in the intuitive sense) can be realized as a Turing machine/ register machine"

 

Our intuitive idea of an algorithm has properties such as:

• Finite description of the procedure in terms of "elementary operations"
• Deterministic (ie next step is uniquely determined)
• Procedure may not terminate on some input data, but can recognize when it does and what the result is

 

The Church-Turing thesis isn't a statement that can be proved formally, as the notion of an algorithm is informal. However, there is empirical evidence that supports the thesis: many alternative formalizations of the intuitive notion of algorithm have turned out to determine the same collection of computable functions.

 

Primitive Recursive Functions

A function is defined to be primitive recursive if and only if it is one of the 5 basic functions or can be obtained from the basic functions by applying the operators a finite number of times.

 

The basic functions:

 

Projection	For every n≥1 and each i with 1≤i≤n, the n-ary projection function Pin, which returns its i-th argument, is primitive recursive.
Constant	The 0-ary constant function 0 is primitive recursive.
Successor	The 1-ary successor function S, which returns the successor of its argument (see Peano postulates), is primitive recursive.

Note: the arity of a function is the number of arguments or operands that the function takes.

Composition of Partial Functions

Composition: Given f, a k-ary primitive recursive function, and k m-ary primitive recursive functions g1,...,gk, the composition of f with g1,...,gk, i.e. the m-ary function h(x1,...,xm) = f(g1(x1,...,xm),...,gk(x1,...,xm)), is primitive recursive.

 

Or as the notes say:

f º (g1,...,gn) is the unique m-ary partial function h satisfying

h(x1,...,xm) = f(g1(x1,...,xm),...,gn(x1,...,xm))

 

 

 

Primitive recusrion

Primitive recursion: Given f, a k-ary primitive recursive function, and g, a (k+2)-ary primitive recursive function, the (k+1)-ary function defined as the primitive recursion of f and g, i.e. the function h where h(0,x₁,...,x_k) = f(x₁,...,x_k) and h(S(n),x₁,...,x_k) = g(h(n,x₁,...,x_k),n,x₁,...,x_k), is primitive recursive.

 

pⁿ(f,g) is the unique (n+1)-ary partial function that:

●      f(x1,...,xn)=y0

●      g(x1,...,xn,i,yi)=y_i+1 for i=0,...,x-1

●      y_x=y

 

If f and g1,...,gn are all computable, then so is f º (g1,...,gn)

If f and g are computable, then so is pⁿ(f,g)

The proofs involve register machine programs F and Gi computing f(y1,...,yn) and gi(xi,...,xm) in R0 .

 

 

Examples of primitive recursion

Addition

Intuitively, addition can be recursively defined with the rules:

add(0,x)=x,

add(n+1,x)=add(n,x)+1.

In order to fit this into a strict primitive recursive definition, define:

add(0,x)=P₁¹(x) ,

add(S(n),x)=S(P₁³(add(n,x),n,x)).

Here P₁³ is the projection function that takes 3 arguments and returns the first one.

P₁¹ is simply the identity function; its inclusion is required by the definition of the primitive recursion operator above; it plays the role of f. The composition of S and P₁³, which is primitive recursive, plays the role of g.

Subtraction

Because primitive recursive functions use natural numbers rather than integers, and the natural numbers are not closed under subtraction, a limited subtraction function is studied in this context. This limited subtraction function sub(a,b) returns b − a if this is nonnegative and returns 0 otherwise.

The predecessor function acts as the opposite of the successor function and is recursively defined by the rules:

pred(0)=0,

pred(n+1)=n.

These rules can be converted into a more formal definition by primitive recursion:

pred(0)=0,

pred(S(n))=P₂²(pred(n),n).

The limited subtraction function is definable from the predecessor function in a manner analogous to the way addition is defined from successor:

sub(0,x)=P₁¹(x),

sub(S(n),x)=pred(P₁³(sub(n,x),n,x)).

Here sub(a,b) corresponds to b-a; for the sake of simplicity, the order of the arguments has been switched from the "standard" definition to fit the requirements of primitive recursion. This could easily be rectified using composition with suitable projections.

Other primitive recursive functions include exponentiation and primality testing. Given primitive recursive functions e, f, g, and h, a function which returns the value of g when e≤f and the value of h otherwise is primitive recursive.

Every primitive recursive function is both computable and total

Note:

To prove every member of PRIM (the set of primitive recursive functions) has property P, it suffices to show that:

●      The 3 basic functions (projection,zero,successor) satisfy P

●      The composition satisfies P

●      If f & g satisfies P then so does pⁿ(f,g)

To prove "Every primitive recursive function is both computable and total" we already know they are computable, and the first two satisfactions are evident.

If f & g are total then for all (x1,...,xn) the definition of pⁿ(f,g) gives pⁿ(f,g)(x1,...,xn,0)ò

 

Partial recursive functions

A partial recursive function is a partial function that can be built up from the basic functions by repeated use of the operations of composition, primitive recursion and minimization.

The set of PR (partial recursive functions) that are total are called total recursive functions.

 

A function f from words to words (over a finite alphabet) is called computable if there exists an method - any method at all - to compute it. It is recursive if it can be computed by a Turing machine; that is, if there exists a Turing machine that accepts every input, and when given input string x, leaves the string f(x) on its tape upon acceptance.

A partial function is called partial recursive if it can be computed by a Turing machine; that is, if there exists a Turing machine that accepts input x exactly when f(x) is defined, in which case it leaves the string f(x) on its tape upon acceptance.

By Church's thesis, a function is recursive if and only if it is computable.

Minimization: the μ operator

"The least value of y -- given y is less than z -- such that R(x, y) is true."

 

μ (f)(x1,...,xn) = { the least x such that

f(x1,...,xn,x)=0 and

f(x1,...,xn,i)>0 for i<x

μ (f)(x1,...,xn)é if no x exists satisfying these conditions.

 

If f is computable, then so is μ (f)

 

Example of minimization:

The everywhere undefined function is partial recursive. for if f(x,y)=1, then μ(f(x)é for all x;

and f=suc º zero²; so μ(f) = μ(f=suc º zero ²) is partial recursive.

 

All primitive recursive functions (PRIM) are partial recursive (PR) and total

but there are total recursive functions which are not primitive recursive

 

Ackermann's Function

Ack is recursive but not primitive recursive

 

ack є Fun(NxN,N) satisfying

ack(0,y) = y+1

ack(x+1,0) = ack(x,1)

ack(x+1,y+1)=ack(x,ack(x+1,y)

 

A partial function is (register machine) computable if & only if it is partial recursive.

 

The proof that a function is partial recursive if it is computable starts on p114.

 

Recursive and recursively enumerable sets

A set S is effectively enumerable if there is some algorithm A which lists the elements of S:

S = { A(0), A(1), A(2), ... }

 

 

The set PR is effectively enumerated by the algorithm A which, given input x,

decodes x as a pair x = <n,e>, then

decodes e as a register machine program Proge,

and returns the n-ary computable (hence partial recursive) function Фeⁿ(x1,...,xn) = y <def> computation of Proge started with R1,...,Rn set to x1,...,xn halts with R0=y.

 

 

A subset S ⊆ N of numbers is recursively enumerable iff either it is empty or there is a (total) recursive function f є Fun(N,N) so that S = { f(n) | n є N }

 

S ⊆ N is decidable iff the characteristic function of S

Xs(X)={ 1 if x є S, 0 if x ! є S

is computable. Such subsets are also called recursive.

 

Every recursive set is recursively enumerable

Since Xs is recursive so is f(x)=ifzero(xs(x),x0,x) and S={f(x) | x є N }, so S is r.e.

 

The set of total functions isn't recursively enumerable,.

 

You can have an r.e. set that isn't recursive:

The halting problem is undecidable, ie not recursive. But H is r.e. because the domain of the partial recursive function f(x)=u(x,0) -u=universal register machine.

 

The following are equivalent

For a subset S ⊆ N:

●      S is recursively enumerable

●      S = Im(f), the image of a unary partial recursive function

●      S = Dom(f), the domain of a unary partial recursive function

●      S is semi-decidable, meaning that the partial function

in_s(x)={1 if x є S

undefined if x ! є S

is partial recursive.

Co-recursive

A subset S ⊆ N is called co-recursive iff N \ S (def { x є N | x є S } ) is r.e.

 

S is recursive iff it is both r.e. and co-re.

 

 

Note

S is countably infinite if there is some bijection (on-one and onto function) between N and S.

S is countable if it is either finite or countably infinite.

S is uncountable if it is not countable.

 

Eg; By Cantor's diagonal slash argument Fun(N,N) is uncountable.