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.
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
ai is the symbol under the read/write head
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.
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)
More information is available in books such as "Elements of Functional
Programming" by Chris Reade.
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.
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.
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). More details about grammars.
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. More details about formal languages.
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" 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
assumption leads to a contradiction. Thus the statement is proven false.
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[100000000]; /* make as big as you want or use malloc */
read_a_C_program_into( I );
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 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?
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.
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.
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.
Last updated 11/30/03