It wasn't always this obvious Why a Universal Machine? it should that the basic logics of a machine If EVAL can simulate any machine, and if EVAL is itself a description of a machine, then EvAL can simulate itself coincide with the logics of a machine intended to make bills This was our example of meal for a department store, I would regard this as the most mazing coincidence that I have ever encountered In fact, EVAL can simulate an evaluator for any other Just need to specify syntax, rules of evaluation ard Aiken, writing in 1956( designer of the Mark I lectronic Brain, developed jointly by IBM and Harvard An evaluator for any language can simulate any other tarting in 1939) language computable in one language is computable in any other language s InsI Iht Turing's insight Alan Mathison Turing ticularthe Led Turing to investigate Hilberts Entscheidungsproblem For many propositions it was easy to find such an algorithm. in proving that for certain propositions no such Is there some fixed definite process which, in principle, E.g, Suppose want to prove some theorem in geometry Consider a proofs from axioms in 1 step in 2 steps Turings insight The halting problem Turing proposed a theoretical model of a simple kind of If there is a problem that the universal machine can't solve (now called a Turing then no machine can solve, and hence no effective process any"effective process" can be carried out by such a Make list of all possible programs (all machines with 1 input) Encode all their possible inputs as integers Each machine can be characterized by its program List their outputs for all possible inputs(as integer, error or Showed how to code a universal machin Define f(n)=output of machine n on input n, plus 1 if output is a number Wrote the first EVAL Define f(n)=0 if machine n on input n is error or loops Yet we just described process for computing f?? Bug is that can't tell if a machine will always halt and produce5 25/33 It wasn’t always this obvious • “If it should turn out that the basic logics of a machine designed for the numerical solution of differential equations coincide with the logics of a machine intended to make bills for a department store, I would regard this as the most amazing coincidence that I have ever encountered” Howard Aiken, writing in 1956 (designer of the Mark I “Electronic Brain”, developed jointly by IBM and Harvard starting in 1939) 26/33 Why a Universal Machine? • If EVAL can simulate any machine, and if EVAL is itself a description of a machine, then EVAL can simulate itself • This was our example of meval • In fact, EVAL can simulate an evaluator for any other language • Just need to specify syntax, rules of evaluation • An evaluator for any language can simulate any other language • Hence there is a general notion of computability – idea that a process can be computed independent of what language we are using, and that anything computable in one language is computable in any other language 27/33 Turing’s insight • Alan Mathison Turing • 1912-1954 28/33 Turing’s insight • Was fascinated by Godel’s incompleteness results in decidability (1933) • In any axiomatic mathematical system there are propositions that cannot be proved or disproved within the axioms of the system • In particular the consistency of the axioms cannot be proved. • Led Turing to investigate Hilbert’s Entscheidungsproblem • Given a mathematical proposition could one find an algorithm which would decide if the proposition was true of false? • For many propositions it was easy to find such an algorithm. • The real difficulty arose in proving that for certain propositions no such algorithm existed. • In general – Is there some fixed definite process which, in principle, can answer any mathematical question? • E.g., Suppose want to prove some theorem in geometry – Consider all proofs from axioms in 1 step – … in 2 steps …. 29/33 Turing’s insight • Turing proposed a theoretical model of a simple kind of machine (now called a Turing machine) and argued that any “effective process” can be carried out by such a machine • Each machine can be characterized by its program • Programs can be coded and used as input to a machine • Showed how to code a universal machine • Wrote the first EVAL! 30/33 The halting problem • If there is a problem that the universal machine can’t solve, then no machine can solve, and hence no effective process • Make list of all possible programs (all machines with 1 input) • Encode all their possible inputs as integers • List their outputs for all possible inputs (as integer, error or loops forever) • Define f(n) = output of machine n on input n, plus 1 if output is a number • Define f(n) = 0 if machine n on input n is error or loops • But f can’t be computed by any program in the list!! • Yet we just described process for computing f?? • Bug is that can’t tell if a machine will always halt and produce an answer