Question? Leave a message!




Turing completeness

Turing completeness
ECE 250 Algorithms and Data Structures Turing Douglas Wilhelm Harder, M.Math. LEL completeness Department of Electrical and Computer Engineering University of Waterloo Waterloo, Ontario, Canada ece.uwaterloo.ca dwharderalumni.uwaterloo.ca © 20062013 by Douglas Wilhelm Harder. Some rights reserved.Turing completeness 2 Outline In this topic, we will: – Ask what is computable – Describe a Turing machine – Define Turing completenessTuring completeness 3 Computability How do we define what is and what is not computable – Is it possible to write a C++ function which cannot be written using Pascal, Java, or C, or vice versa – For example, do pointers (not available in Java) make C++ more powerful than Java – Is BASIC really that badTuring completeness 4 Computability Consider INTERCAL – 16bit integers .1 … .65535 – 32bit integers ,1 … ,65535 – Arrays of 16bit integers :1 … :65535 – Arrays of 32bit integers ;1 … ;65535 – Each variable has its own stack • You can push the current value onto the stack, or pop back a previous value – There are five operations: interleave, select, and, or, xor Can you do everything you do in C in INTERCAL and vice versaTuring completeness 5 Computability Does computability depend on the processor – The VAX had a machine instruction POLY for polynomial evaluation using Horner’s rule – Is the instruction set of the Intel Core 2 processor significantly different from the Motorola MC6800Turing completeness 6 Computability To study computability, Alan Turing developed a simple and basic but surprisingly powerful symbolmanipulating device: – He called it the amachine (for automatic) – It has since been christened the Turing machine – First described in 1936 • Five years before the first computer (the Z3)Turing completeness 7 Computability The Turing machine has four components: – An arbitrarylength tape • Divided into linearlyordered entries • Each entry is from a finite alphabet G which usually includes a blank B • In this example, G = B, 0, 1Turing completeness 8 Computability The Turing machine has four components: – An arbitrarylength tape – A head that can • Read a symbol off the tape, • Write a symbol to the tape, and/or • Move to the next entry to the left or the rightTuring completeness 9 Computability The Turing machine has four components: – An arbitrarylength tape – A head – A state • The state is one of a finite set of symbols Q • In this example, Q = b, c, e, f • The initial state of the machine is denoted q∈ Q 0 • Certain states may halt the computationTuring completeness 10 Computability The Turing machine has four components: – An arbitrarylength tape – A head – A state Current New Symbol Symbol – A transition table State State Direction read to write • Q ×G → Q ×G × L, R, N b B c 0 R • L moves one entry to the left c B e B R • R moves one entry to the right e B f 1 R • N indicates no shift f B b B R There is at most one entry in this table for each pair of current settingsTuring completeness 11 Computability Currently, the state is e and the symbol under the head is B Current Next Symbol Symbol State State Direction read to write b B c 0 R c B e B R e B f 1 R f B b B RTuring completeness 12 Computability The transition table dictates that the machine must: – The state is set to f – Print symbol 1 onto the tape – Move one entry to the right Current Next Symbol Symbol State State Direction read to write b B c 0 R c B e B R e B f 1 R f B b B RTuring completeness 13 Computability The state and symbol under the head have been updated Current Next Symbol Symbol State State Direction read to write b B c 0 R c B e B R e B f 1 R f B b B RTuring completeness 14 Computability The state is f and the symbol under the head is the blank B:t – The state is set to b – A blank is printed to the tape – Move one entry to the right Current Next Symbol Symbol State State Direction read to write b B c 0 R c B e B R e B f 1 R f B b B RTuring completeness 15 Computability Again, the state is b, the symbol a blank, and therefore: – Set the state to c – Print the symbol 0 to the tape – Move one entry to the right Current Next Symbol Symbol State State Direction read to write b B c 0 R c B e B R e B f 1 R f B b B RTuring completeness 16 Computability The result is the state c and a blank symbol is under the head: – Set the state to e – Write a blank to the tape – Move one entry to the right Current Next Symbol Symbol State State Direction read to write b B c 0 R c B e B R e B f 1 R f B b B RTuring completeness 17 Computability The result is the state e and a blank symbol B under the head – This is the state we were in four steps ago – This machine never halts... Current Next Symbol Symbol State State Direction read to write b B c 0 R c B e B R e B f 1 R f B b B RTuring completeness 18 Computability This was Turing’s first example in his 1937 paper On Computable Numbers, with an Application to the Enscheidungsproblem – It demonstrates a machine which can compute the sequence 0 1 0 1 0 1 0 ···Turing completeness 19 Computability This Turing machine adds two numbers: – Tape symbols:G = B, 1 – States: Q = a, b, c, d, e, H – Initial state: q = a 0 Current Next – Halting state: H Symbol Symbol State State Direction read to write a B a B R Note there is exactly one entry a 1 b 1 R for each pair in Q \ H ×G b B c 1 R – It may not be necessary to have b 1 b 1 R one for each, but you cannot have c B d B L more than one transition for a given state and symbol c 1 b 1 R d B d B L d 1 e B L e B H B R e 1 e 1 LTuring completeness 20 Computability After 22 steps, a group of five ones and a group of six ones are merged into a single group of eleven ones – This represents 5 + 6 = 11Turing completeness 21 Computability What’s more remarkable is the TuringChurch thesis: – For any algorithm which can be calculated given arbitrary amounts of time and storage, there is an equivalent Turing machine for that algorithm This is a hypothesis; however, almost a century has not produced any counterexamples A computational system – e.g., a programming language compiled into machine code and run on a processor is said to be Turing complete if it can compute every function computable on a Turing machineTuring completeness 22 Computability The converse appears to be true, too: – Any function in any Turing complete computational system can also be computed using an appropriate Turing machine – Modern computers are faster, but they are not more powerful than a Turing machine Thus, the Turing machine well defines the concept of computability as it is understood todayTuring completeness 23 Computability Looking at some of the first computers, not all were Turing complete: Decimal/ Turing Name Date Place Electronic Programmable Complete Binary Zuse Z3 1941 Germany binary No Yes Yes AlanasoffBerry Computer 1941 USA binary Yes No No Colossus 1943 UK binary Yes Partially No IBM ASCC 1944 USA decimal No Yes Yes 1944 USA decimal Yes Partially Yes ENIAC 1948 USA decimal Yes Yes Yes Incidentally, Zuse was a civil engineer... http://en.wikipedia.org/wiki/ComputersTuring completeness 24 Computability All modern programming languages are also Turing equivalent – thus, BASIC and C are no worse than Java or C++Turing completeness 25 Computability Some are, practically speaking, less useful: – this is a Turingcomplete language with eight singlecharacter commands – for the C++ equivalence, declare char ptr; Char Operation C++ Equivalent ++ptr; increment the pointer ptr; decrement the pointer + ++(ptr); increment the byte at the pointer – (ptr); decrement the byte at the pointer . putchar(ptr); output the value the byte , ptr = getchar(); input one byte and store it at the pointer jump forward to the command after the matching while( ptr ) if the byte at the pointer is zero jump back to the command after the matching if the byte at the pointer is nonzero http://en.wikipedia.org/wiki/BrainfuckTuring completeness 26 References Wikipedia, http://en.wikipedia.org/wiki/Computability Wikipedia, http://en.wikipedia.org/wiki/Turingmachine Wikipedia, http://en.wikipedia.org/wiki/Church–Turingthesis These slides are provided for the ECE 250 Algorithms and Data Structures course. The material in it reflects Douglas W. Harder’s best judgment in light of the information available to him at the time of preparation. Any reliance on these course slides by any party for any other purpose are the responsibility of such parties. Douglas W. Harder accepts no responsibility for damages, if any, suffered by any party as a result of decisions made or actions based on these course slides for any other purpose than that for which it was intended.