Transcript Computability

Computability
Go over homework problems.
Godel numbering.
Homework: prepare for midterm.
TM for Neat addition
• Create function TM that adds two numbers
and returns as answer all 1s starting from
the left end of the tape, no blanks.
????
TM for multiplication
• Tape starts with two sets of 1s, recall n+1
1 for number n.
• Follow example for addition.
• Consider using markers on tape.
????
TM to tidy up…
• Claim: we can create quintuples to add to
any TM to re-format and modify outputs to
facilitate composition
– output for N is N 1s anywhere on tape.
Change to (N+1) 1s.
– insert or remove marker symbols separating
numbers to be proper inputs.
Reprise: Recursive functions
• The recursive functions are a set of
functions defined using a starter set and
allowing any functions that can be defined
using a finite number of applications of
composition, primitive recursion, and
minimalization
Starter set
• Identity F(x) = x This is special case of
Projections Uin(x1, x2,…,xn) = xi
• Successor S(x) = x+1
• Constant Fc(x) = c
Composition
• Given F and G, FG (x) = F(G(x))
Primitive recursion
• Motivation similar to mathematical
induction, definition of factorial,
exponentiation.
– Have definition for the zero case. Have way
for building.
• x0 = 1
x(n+1) = xn * x
Primitive recursion
• Given functions f: N → N and g: (N,N,N)
→N, then define h: (N,N) as follows
h(x,0) = f(x)
h(x,y+1) = g(x,y,h(x,y))
• You will see variations. For example, f: Nn
and g: Nn+2
Minimalization
• Better name MAY be inverse.
• If f(x) is recursive, then define g to be
g(y) = min {x | f(x) = y} if any x exists.
Otherwise,
g(y) is undefined.
Multiplication
• … is recursive. Can be defined by use of
composition, primitive recursion,
minimalization of other recursive functions.
• Can assume addition!
????
Subtraction
• …is recursive. Can be defined by use of
composition, primitive recursion,
minimalization of other recursive functions.
• Can assume addition!
• Hint: use minimalization
????
Equivalence of TMs and Recursive
functions
• If a function is recursive, then we can
construct a TM for it.
– Build TM for starter sets. Assume fix-up function
to get things in proper format for next step.
– Describe process for doing composition, primitive
recursion, and minimalization.
• Minimalization: given function f for which there is a TM,
call it F, then build a TM that calls F in turn for 0, 1, 2,
….
TM to Recursive
• Need to come up with encoding for TM
that can be decoded to 'do' the steps as a
function.
– Gödel Numbering !
• Prove set of steps that are recursive that
lead to the existence of a computation
using the steps of TM
Arithmetization of [theory of] Turing
machines
• Symbols of TM are:
– symbols available to be on tape: B=S0, S1,…
– R and L
– states: q1,q2…
• Assign odd numbers starting with 3 to
R,L,S0,q1,S1,q2,S2,…
• So quadruples q11Rq2 is represented by
9,11,3,13. The instantaneous description:
q11111 is represented by 9,11,11,11
Arithmetization, cont.
• Gödel Number of expression represented by
sequence of n numbers a1,a2,..,an is the
product of the first n primes, each raised to the
corresponding ak power!
• gn(q11Rq2) = 29 * 311* 53* 713
• gn(sequence of n expressions) = product of the
first n primes each raised to the gn of each
expression
• Note: gn's are either an expression or a
sequence of expressions. gn's are huge! gn's
are unique—can get back to expression or
sequence.
Arithmetization, cont.
• Take any Turing Machine. (Using
quadruples in place of quintuples. The
operation of writing is distinct from moving
left or right).
• TM defines by its set of quadruples.
• Define a gn for a TM is the gn for a
sequence of its quadruples. So different
orders will produce different gn.
Computation
• A computation is a sequence s1,…sk of
expressions representing steps of a TM
operating on input
– starting with q1 followed by input
– sequence, sisi+1, according to TM
– sk is terminal (final, no next step)
Description of proof
• With a gn for TM T, show by a set of steps
involving what are valid computations
starting from expression representing
initial state in front of input, that a
recursive function exists that has same
behavior as T on the input.
Predicate
• A predicate is a function of 1 or more
parameters that returns true or false.
• Proof shows that a certain predicate is
primitive recursive (that is, in the set
starting with the starting functions and with
any functions added using primitive
recursion and composition)
Predicate
• T(z,x1, x2, … xn,y) is true if
z is the gn for a TM
x1, x2, .. xn are the inputs
y is a computation
of the TM encoded by z
• T(x,x1,x2, … , xn, y) is false, otherwise,
including z or y not being gn for any TM or
any computation.
Claim
• By many steps, can show T to be primitive
recursive
• Example, Yield(x,y,z) is defined as the
predicate, such that
if x and y are gn for instantaneous expressions
and z is gn for a TM and x  y for TM z, then
true,
Otherwise, false
Define function in 2 steps
Then
Vz(x1,…xn) defined as
min y | T (z,x1, … xn, y)
is recursive.
Note: at most one such y.
Last step
U(y), defined as: if y is a computation,
number of 1s in last expression of y.
Undefined, otherwise. This can be shown
to be primitive recursive.
Then
U(min y | T (z,x1, … xn, y) ) is recursive
Comments
•
•
•
•
The predicate T is very powerful.
It is false most of the time.
It does the job for ALL TMs.
For any particular function computed by a
particular TM, there would be a more efficient
recursive function.
• The steps are based on the mechanistic feature
of TMs.
• There are other formulations equivalent to these
two (TMs and recursive functions).
More Topics
• Implementation of TM (language recognizer or
function) in code
– there exists on-line examples
• Gödel work on incompleteness of logical
systems
• Other equivalent formulations for computability
• computable numbers
• Work on randomness and computability
– Greg Chaitin, others.
• others cited previously
Homework
• Review midterm guide.
• Study charts.
• Come with questions based on your
review.