Monday 24 June 2013

Definitions of computable

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.

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.

No comments:

Post a Comment