## Definitions of computable

### Contents

• Church's Hypothesis on Computable
• Turing Machines
• Lambda Calculus
• Post Formal Systems
• Partial Recursive Functions
• Unrestricted Grammars
• Formal Languages
• Functions
• The Halting Problem
• Decision Problems
• Godel Incompleteness Theorem
• Unsolvable
• Undecidable
• ### Church's hypothesis, Church Turing Thesis

```  This is a mathematically unprovable belief that a reasonable intuitive
definition of "computable" is equivalent to the list provably equivalent
formal models of computation:

Turing machines

Lambda Calculus

Post Formal Systems

Partial Recursive Functions

Unrestricted Grammars

Recursively Enumerable Languages

and intuitively what is computable by a computer program written in any
reasonable programming language.
```

### Turing Machines

```  A basic Turing machine is a model for studying computation.
Turing machines can solve decision problems and compute results based
on inputs.  When studying computation we usually restrict our attention
to integers.  Since a real number has infinitely many fraction digits we
can not compute a real number in a finite time.  Rational numbers a
approximations to real numbers are equivalent and can be put in
one-to-one correspondence with the integers.

Programming a Turing machine is tedious and thus much work
at higher levels of abstraction make the reasonable assumption that
any completely defined algorithm or computer program could be
implemented by a Turing machine.

The Turing Machine Model is
M = ( Q, Sigma, Gamma, delta, q0, B,  F)

Q = finite set of states including q0
Sigma = finite set of input symbols not including B
Gamma = finite set of tape symbols including Sigma and B
delta = transitions mapping  Q x Gamma to Q x Gamma x {L,R}
q0    = initial state
B     = blank tape symbol, initially on all tape not used for input
F     = set of final states

+---------------------+-----------------
| input string        |BBBBB ...  accepts Recursively Enumerable Languages
+---------------------+-----------------
^ read and write, move left and right
|
|  +-----+
|  |     |--> accept
+--+ FSM |
|     |--> reject
+-----+

+-------------------------+-----------------
| input and output string |BBBBB ...  computes partial recursive functions
+-------------------------+-----------------
^ read and write, move left and right
|
|  +-----+
|  |     |
+--+ FSM |--> done  (a delta [q,a]->[empty], but may never happen )
|     |
+-----+

delta is a table or list of the form:
[qi, ai] -> [qj, aj, L]   or  [qi, ai] -> [qj, aj, R]

qi is the present state

qj is the next state
aj is written to the tape at the present position
L  is move the read/write head left one position after the write
R  is move the read/write head right one position after the write

There are a lot of possible Turing machines and a useful technique
is to code Turing machines as binary integers. A trivial coding is
to use the 8 bit ASCII for each character in the written description
of a Turing machine concatenated into one long bit stream.
Having encoded a specific Turing machine as a binary integer, we
can talk about  TMi  as the Turing machine encoded as the number "i".

It turns out that the set of all Turing machines is countable and
enumerable.

Now we can construct a Universal Turing Machine, UTM, that takes
an encoded Turing machine on its input tape followed by normal
Turing machine input data on that same input tape. The Universal Turing
Machine first reads the description of the Turing machine on the
input tape and uses this description to simulate the Turing machines
actions on the following input data. Of course a UTM is a TM and can
thus be encoded as a binary integer, so a UTM can read a UTM from
the input tape, read a TM from the input tape, then read the input
data from the input tape and proceed to simulate the UTM that is
simulating the TM.  Etc. Etc. Etc.

Since a UTM can be represented as an integer and can thus also
be the input data on the input tape of itself or another Turing
machine. This will be used below in the Halting Problem.

```

### Lambda Calculus

```  Also known as Church's Lambda Calculus, we describe here the
non pure form which has constants.

An expression in the Lambda Calculus, E, is defined as

E ::= C | V | (E1E2) | (\vE1) | (E1)    where

C  = {a set of constants including untyped values and function names}
V  = {finite set of variables}
Ei = {a set of lambda terms called expressions}

A Lambda Expression is one of the following:

1) a constant from C
2) a variable from V
3) a combination involving the application of expression E1 to
another expression E2.  E1 is the operator and E2 is the
operand.
4) an abstraction involving a variable v from V and an expression E1.
\vE1  v is called the bound variable and E1 is the body.
5) parentheses, (E1) are not really needed but are allowed to
make it easier to read Lambda Expressions. A period may also
be used to separate the bound variable from the body as \v.E1
(Note that the small Greek letter Lambda is typed as a backslash.)
E1E2E3...En means  ((...((E1E2)E3)...)En)

A beta reduction is (\v.E1)E2 -> E1[E2/v] which says E2 is substituted
for all free occurrences of v in E1.

An eta reduction is  \v.Ev -> E  provided v is not free in E.

Example: (\x.plus x 1)((\y.times y y)3) => plus(times 3 3)1  which equals 10

Various orders of evaluation are possible, one of the most used is
leftmost-outermost (normal form order)(safe)

```

### Post Formal Systems

```  This is somewhat similar to formal grammars yet is has an easier
conversion to Turing machines and uses the concept of axioms.

A Post System  Pi = (C, V, A, P)  where
C = {non terminal constants} union {terminal constants}
V = {finite set of variables}
A = {a finite set from C*, called the axioms}
P = finite list of productions of the form:
x1 v1 x2 ... xn vn xn+1 -> y1 w1 y2 ... yn wn yn+1  where
xi and yi are in C*
vi and wi are in V  with restriction wi /= wj saying that a
variable may appear at most once on the left
union wi is a subset of union vi, saying that each variable wi on
the right must appear on the left

Post Systems can express arithmetic, as in the example:

Ct = { 1, +, = }
Cn = Phi
V  = {v1, v2, v3}
A  = { 1 + 1 = 11 }    tally notation for one plus one equals two

P1   v1 + v2 = v3  ->  v1 1 + v2 = v3 1
P2   v1 + v2 = v3  ->  v1 + v2 1 = v3 1

The example system allows the derivations

1 + 1 = 11  =>  11 + 1 = 111         by P1  1+1=2 => 2+1=3
=>  11 + 11 = 1111       by P2  2+2=4
=>  111 + 11 = 11111     by P1  3+2=5
=>  111 + 111 = 111111   by P2  3+3=6     etc.
```

### Partial recursive functions

```  A Partial Recursive Function is allowed to have an infinite loop
for some input values. A Recursive Function also called a Total
Recursive Function always returns a value for all possible
input values.

Partial Recursive Functions correspond to Turing machines that may
not halt. (Total) Recursive Function correspond to Turing machines
that always halt.

Primitive Recursive Functions are a subset of Total Recursive Functions
with the restriction that only primitive recursion is used a finite
number of times and recursion uses zero and the successor function.

Primitive recursion is defined for f(x1,...,xn) as
f(x1,...,xn) = g(x1,...,xn-1)                     if xn = 0
= h(x1,...,xn,f(x1,...,xn-1, xn -1)) if xn > 0
where g and h are primitive recursive functions.
Ackermann's function is not primitive recursive.

For technical reasons a projection function, a selector, is often
used. Pi(x1,...,xn) returns xi where  1 <= i <= n.

y = f(x1,...,xn) is a partial recursive function over the natural
numbers when f is defined by a finite set of rules using a finite
set of variables and a finite set of constants from the set of
natural numbers. The function f can make use of itself and other
partial recursive functions. A typical base function is the
successor function, add one, and the constants typically include zero.
The arguments x1,...xn and the result value y are from the set of
natural numbers.

This can be extended to partial recursive functions over the integers
and over the rational numbers, ratio of two integers,
but can not be extended to the set of real numbers. y=f(x) is not
a partial recursive function when x and y are from the set of
real numbers and f(x) is defined as the square root of x, also written
as the value of y that satisfies  y**2 = x  or  y**2 - x = 0.
For example, when x = 2, y is the square root of 2 which can not
be computed in a finite time and yet is a well defined value for
a real number.
```

### Unrestricted grammars

```  A grammar is another way to pose a  decision problem.
A grammar takes a string as input and accepts or rejects the string.
Thus a grammar characterizes a language, usually written  L(G).

```

### Formal Languages

```  A formal language is defined as set of finite strings over an alphabet
of finite symbols.  A decision problem can be posed as given a language
is a given string in the language.  Basically this is the mathematical
problem of given a set is a particular element in the set.

```

### Functions

```  A function is a mapping from a domain to a range.
A total function outputs something for every input.
A partial function may to produce an output for only some inputs.
By grouping the inputs, any function with more than one input can be
represented by a function with only one input.  Ditto for output.
A computable function may be expressed in many forms, yet to be
reasonable, the function must be finite.  Thus all functions can be
expressed as a subset of sigma star for some finite alphabet sigma.
The set of all computable functions is countable.
The range of a function can be a subset of real numbers, but the real
numbers are uncountable, thus there are real numbers not computable by
any function.
A mapping can be defined for which there is no computable function.

Functions are some times categorized by the relations of the domain
and range. The terms injection, surjection and bijection are all total
functions defined as:

Injection :  one-to-one into : for every member of the domain, the
function returns some member of the range, but not
necessarily all members of the range will be returned.

Surjection : many-to-one onto : for every member of the domain, the
function returns some member of the range. Every member
of the range is returned for some member of the domain, but
unique members of the domain may return the same member
of the range.

Bijection :  one-to-one onto : for every member of the domain, the
function returns a unique member of the range.

Inverse :    The inverse function of some function has the domain
and range interchanged. The inverse of a Bijection is
a Bijection. Inverse functions do not exists for general
Injection or surjection functions.

Example:     y = sin(x)  computer approximation of trigonometric sine
function
y is a member of the Range -1.0..+1.0 floating point values
x is a member of the Domain of all floating point values
sin is a Surjection function, many-to-one onto
```

### The Halting Problem

```
The "Halting Problem" is a very strong, provably correct, statement
that no one will ever be able to write a computer program or design
a Turing machine that can determine if a arbitrary program will
halt (stop, exit) for a given input.

This is NOT saying that some programs or some Turing machines can not
be analyzed to determine that they, for example, always halt.

The Halting Problem says that no computer program or Turing machine
can determine if ALL computer programs or Turing machines will halt
or not halt on ALL inputs. To prove the Halting Problem is
unsolvable we will construct one program and one input for which
there is no computer program or Turing machine.

We will use very powerful mathematical concepts and do the proofs
for both a computer program and a Turing machine. The mathematical
concepts we need are:

Proof by contradiction. Assume a statement is true, show that the

Self referral. Have a computer program or a Turing machine operate
on itself, well, a copy of itself, as input data. Specifically we
will use diagonalization, taking the enumeration of Turing machines
and using TMi as input to TMi.

Logical negation. Take a black box that accepts input and outputs
true or false, put that black box in a bigger black box that
switches the output so it is false or true respectively.

The simplest demonstration of how to use these mathematical concepts
to get an unsolvable problem is to write on the front and back of
a piece of paper "The statement on the back of this paper is false."
Starting on side 1, you could choose "True" and thus deduce side 2
is "False". But staring on side 2, which is exactly the same as
side 1, you get that side 2 is "True" and side 1 is "False."
Since side 1, and side 2, can be both "True" and "False" there
is a contradiction. The problem of determining if sides 1 and 2 are
"True" of "False" is unsolvable.

The Halting Problem for a programming language. We will use the "C"
programming language, yet any language will work.

Assumption: There exists a way to write a function named Halts such that:

int Halts(char * P, char * I)
{
/* code that reads the source code for a "C" program, P,
determines that P is a legal program, then determines if P
eventually halts (or exits) when P reads the input string I,
and finally sets a variable "halt" to 1 if P halts on input I,
else sets "halt" to 0 */
return halt;
}

Construct a program called Diagonal.c as follows:

int main()
{
char I;          /* make as big as you want or use malloc */
if ( Halts(I,I) )  { while(1){} } /* loop forever,means does not halt */
else return 1;
}

Compile and link Diagonal.c into the executable program Diagonal.
Now execute
Diagonal < Diagonal.c

Consider two mutually exclusive cases:
Case 1: Halts(I,I) returns a value 1.
This means, by the definition of Halts, that Diagonal.c halts
when given the input Diagonal.c.
BUT! we are running Diagonal.c (having been compiled and linked)
and so we see that Halts(I,I) returns a value 1 causes the "if"
statement to be true and the  "while(1){}" statement to be
executed, which never halts, thus our executing Diagonal.c
does NOT halt.
This is a contradiction because this case says that Diagonal.c
does halt when given input Diagonal.c.
Well, try the other case.

Case 2: Halts(I,I) returns a value 0.
This means, by the definition of halts, that Diagonal.c does NOT
halt when given the input Diagonal.c.
BUT! we are running Diagonal.c (having been compiled and linked)
and so we see that Halts(I,I) returns a value 0 causes the "else"
to be executed and the main function halts (stops, exits).
This is a contradiction because this case says that Diagonal.c
does NOT halt when given input Diagonal.c.
There are no other cases, Halts can only return 1 or 0.
Thus what must be wrong is our assumption "there exists a way
to write a function named Halts..."

The Halting Problem for Turing machines.

Assumption: There exists a Turing machine, TMh, such that:
When the input tape contains the encoding of a Turing machine, TMj
followed by input data k, TMh accepts if TMj halts with input k
and TMh rejects if TMj is not a Turing machine or TMj does not halt
with input k.

Note that TMh always halts and either accepts or rejects.
Pictorially TMh is:

+----------------------------
| encoded TMj B k BBBBB ...
+----------------------------
^ read and write, move left and right
|
|  +-----+
|  |     |--> accept
+--+ FSM |                     always halts
|     |--> reject
+-----+

We now use the machine TMh to construct another Turing machine TMi.
We take the Finite State Machine, FSM, from TMh and
1) make none of its states be final states
2) add a non final state ql that on all inputs goes to ql
3) add a final state qf that is the accepting state

Pictorially  TMi is:

+-------------------------------------------
| encoded TMj B k BBBBB ...
+-------------------------------------------
^ read and write, move left and right
|
|  +----------------------------------+
|  |                      __          |
|  |                     /   \ 0,1    |
|  |                   +-| ql |--+    |
|  | +-----+           | \___/   |    |
|  | |     |--> accept-+   ^     |    |
+--+-+ FSM |               |_____|    |            may not halt
| |     |--> reject-+    _         |
| +-----+           |  // \\       |
|                   +-||qf ||------|--> accept
|                      \\_//       |
+----------------------------------+

We now have Turing machine TMi operate on a tape that has TMi as
the input machine and TMi as the input data.

+-------------------------------------------
| encoded TMi B encoded TMi BBBBB ...
+-------------------------------------------
^ read and write, move left and right
|
|  +----------------------------------+
|  |                      __          |
|  |                     /   \ 0,1    |
|  |                   +-| ql |--+    |
|  | +-----+           | \___/   |    |
|  | |     |--> accept-+   ^     |    |
+--+-+ FSM |               |_____|    |            may not halt
| |     |--> reject-+    _         |
| +-----+           |  // \\       |
|                   +-||qf ||------|--> accept
|                      \\_//       |
+----------------------------------+

Consider two mutually exclusive cases:
Case 1: The FSM accepts thus TMi enters the state ql.
This means,by the definition of TMh that TMi halts with input TMi.
BUT! we are running TMi on input TMi with input TMi
and so we see that the FSM accepting causes TMi to loop forever
thus NOT halting.
This is a contradiction because this case says that TMi
does halt when given input TMi with input TMi.
Well, try the other case.

Case 2: The FSM rejects thus TMi enters the state qf.
This means, by the definition of TMh that TMi does NOT halt with
input TMi.
BUT! we are running TMi on input TMi with input TMi
and so we see that the FSM rejecting cause TMi to accept and halt.
This is a contradiction because this case says that TMi
does NOT halt when given input TMi with input TMi.
There are no other cases, FSM either accepts or rejects.
Thus what must be wrong is our assumption "there exists a
Turing machine, TMh, such that..."
QED.

Thus we have proved that no Turing machine TMh can ever be created
that can be given the encoding of any Turing machine, TMj, and any input,
k, and always determine if TMj halts on input k.

```

### Decision Problems

```  Decision problems are stated as questions where the answer is binary,
0 or 1, False or True, No or yes, Reject or Accept and so forth.

Generally a decision problem states a problem and gives a candidate
solution, asking if the solution solves the problem.
Examples:
Given the math expression  2+2  is the answer 4?
Given a formal language and a string, is the string in the language?
Given a grammar and a string, is the string accepted by the grammar?
```

### Godel Incompleteness Theorem

```  Any formal system powerful enough to express arithmetic must have
true theorems that can not be proven within the formal system.

Basically Godel proved that when trying to add axioms to a formal system
in order to prove all true theorems within the formal system, eventually
the system will become inconsistent before is becomes complete.

A complete formal system is a formal system where all true theorems
can be proved.

An inconsistent formal system is a formal system where at least one
false statement can be proved within the formal system.

Due to the computational equivalence of formal systems to other
computational capability, we get the Halting problem, the
uncomputable numbers and other unsolvable problems.
```

### Unsolvable

```  A formally stated problem is Unsolvable
if no Turing machine exists to compute the solution.

A formally stated problem is provably unsolvable
if it can be proved no Turing machine exists to compute the solution.
```

### Undecidable

```  A formally stated problem is Undecidable if no total recursive function
and thus, no Turing machine that always halts, can be constructed
to decide the problem, usually true or false.

```