Computability
The issue of exactly what
computers can compute and what they cannot.
Tool:
1.
Turing machines: Traditional
Quadruples (One
version)
Qi
Sj
Sk
Ql
Qi
Sj
R
Ql
Qi
Sj
L
Ql
Very tedious and difficult
to analyze
2.
A SIMPLE Language: Our textbook
Less tedious and not
so difficult to analyze.
A SIMPLE
Language
1.
Numeric processing: Only non-negative integers
2.
Variables:
X1, X2, X3, ...
Input variables that assume intended input values
each.
Y
Only one output variable initialized to zero
Z1, Z2, Z3, ...
Local variables initialized to zero each
3.
Three basic statements:
V =
V+1
// same variable
V =
V-1
// same variable, 0-1 is
0
IF V <> 0 GOTO L
// L is the Lable of the destination statement
4.
Some Macros : to make the language more powerful without changing the
very
definition of the language.
GOTO L
V = 0
V1 = V2
V1 = V2 + V3
V1 = V2 – V3
V1 = V1 * V3
5.
Example Macro Expansions
GOTO L
Zi = Zi +1
IF Zi <> 0 GOTO L
V = 0
[A]
V = V-1
IF V <> 0 GOTO
A
V1 = V2 (V2 should not be changed in the process)
V1 = 0
[A]
IF V2 <> 0 GOTO
B
GOTO C
[B]
V2 = V2 - 1
V1 = V1 + 1
V3 = V3 + 1
// A new local variable
GOTO A
[C]
IF V3 <> 0 GOTO D
GOTO E
// Done
[D]
V3 = V3 – 1
V2 = V2 + 1
GOTO C
V1 = V2 + V3 (V2 and V3 must remain the same and V1 and V3 are
distinct)
V1 = V2
V4 = V3
// V4 is a new local variable
[B]
IF V4 <> 0 GOTO
A
GOTO E
// done
[A]
V1 = V1 + 1
V4 = V4 – 1
GOTO B
Program
execution
1.
State
A list of equations of form V=m where V is a variable and m its
current
for all variables of a program.
Exactly one equation for each variable.
So, a state of a program represents a current computational
result.
2.
Snapshot (Instantaneous Description)
s = (i, state)
where i is the next instruction to be executed and
initially it is 1 when a program is about to start.
When i is n+1 (where n is the number of instructions of a
program)
the program stops.
3.
Terminal snapshot
When the first component of a snapshot is n+1 indicating that
the
Program is about to stop.
4.
Successor snapshot (j, state2) of a non-terminal snapshot
(i,state1)
a.
case-1: i-th instruction is V = V+1
j = i+1
The equation V=m of state1 will be replaced by the
equation
V = m+1 and the result becomes state2.
b.
case-2: i-th instruction is V = V-1
j = i+1
The equation V=m of state1 will be replaced by the
equation
V = m-1 if m>0 or V=0 if m=0 and the reuslt becomes
state2.
c.
case-3: i-th instruction is IF V<>0 GOTO L
Two subcases (in both cases, state2 becomes the same as
state1)
3a: when V=0 is an equation of state1.
j=i+1 and state2 is the same as state1
3b: when the equation V=m of state1 has m>0
i. when at least one instruction of the
program has the label L
j will become the least number of an instruction with label
L
ii. when no
instruction of the program has the label L
j = n+1
(Terminal snapshot for the program to terminate)
Partially Computable
Functions
We associate each program P with m
inputs, X1, X2, ..., and Xm with a function of
as many arguments (m) as
follows:
1. Y = yP (X1, X2, ..., Xm) is a
partially computable function
2. The value of this function is the same as the value of the output
variable Y
of this program
P whenever the program terminates, i.e., whenever there is
a
computation to
this program.
3. When there is no computation, i.e., there is no terminal snapshot,
or
when the
program does not terminate, the value of this function is
undefined.
Computable
functions:
Partially computable functions that are total (defined for all possible
arguments
values).
So, by definition, a program computing a Computable function must
terminate
in all cases, i.e., for all possible inputs.
Example:
P1
Y = X1
[A]
IF X2 = 0 GOTO
E
Y = Y+1
Y = Y+1
X2 = X2-1
GOTO A
yP1 (X1,X2) = X1 + 2*X2 which is
total and hence computable.
Example:
P2
Y = X1
[A]
IF X2 = 0 GOTO
E
X2 = X2 – 1
[B]
IF X2 = 0 GOTO B
Y = Y+1
Y = Y+1
Y = Y+1
Y = Y+1
X2 = X2 - 1
GOTO A
yP2 (X1,X2) = X1 + 2*X2 if X2 is even and undefined otherwise.
So, this function is partially computable but not computable.
Note that the program does not terminate if X2 is odd.