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
  • Other Links
  • 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
      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.
    
    

    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)
    
      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.
    

    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,
       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.
    

    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

      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. 
    

    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 string in the set.
    
       More details about formal languages. 
    
    

    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
      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

      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.
    
    

    Other Links

    Go to top

    Last updated 6/26/12