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) The result or applying reductions to a Lambda expression can be a number, a string, a picture, basically anything that is computable. 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, read as monadic numbers 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.
An Unrestricted grammar G = (V, T, P, S) has a finite set of Variables, a finite set of Terminals, a finite set of Productions and a Starting or goal Variable. Productions are of the form A -> w, where A and w are any concatenation of Variables and Terminals. For every recursively enumerable set there is an unrestricted grammar. Thus a grammar defines a language, usually written L(G). A grammar is another way to pose a decision problem. A grammar takes a string as input and accepts or rejects the string. 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 string 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 6/26/12