Create Presentation
Download Presentation

Download Presentation
## A Universal Turing Machine

- - - - - - - - - - - - - - - - - - - - - - - - - - - E N D - - - - - - - - - - - - - - - - - - - - - - - - - - -

**A Universal Turing Machine**Prof. Busch - LSU**A limitation of Turing Machines:**Turing Machines are “hardwired” they execute only one program Real Computers are re-programmable Prof. Busch - LSU**Solution:**Universal Turing Machine Attributes: • Reprogrammable machine • Simulates any other Turing Machine Prof. Busch - LSU**Universal Turing Machine**simulates any Turing Machine Input of Universal Turing Machine: Description of transitions of Input string of Prof. Busch - LSU**Tape 1**Three tapes Description of Universal Turing Machine Tape 2 Tape Contents of Tape 3 State of Prof. Busch - LSU**Tape 1**Description of We describe Turing machine as a string of symbols: We encode as a string of symbols Prof. Busch - LSU**Alphabet Encoding**Symbols: Encoding: Prof. Busch - LSU**State Encoding**States: Encoding: Head Move Encoding Move: Encoding: Prof. Busch - LSU**Transition Encoding**Transition: Encoding: separator Prof. Busch - LSU**Turing Machine Encoding**Transitions: Encoding: separator Prof. Busch - LSU**Tape 1 contents of Universal Turing Machine:**binary encoding of the simulated machine Tape 1 Prof. Busch - LSU**A Turing Machine is described**with a binary string of 0’s and 1’s Therefore: The set of Turing machines forms a language: each string of this language is the binary encoding of a Turing Machine Prof. Busch - LSU**Language of Turing Machines**(Turing Machine 1) L = {010100101, 00100100101111, 111010011110010101, ……} (Turing Machine 2) …… Prof. Busch - LSU**Countable Sets**Prof. Busch - LSU**Infinite sets are either:**• Countable • or • Uncountable Prof. Busch - LSU**Countable set:**There is a one to one correspondence of elements of the set to Natural numbers (Positive Integers) (every element of the set is mapped to a number such that no two elements are mapped to same number) Prof. Busch - LSU**Example:**The set of even integers is countable Even integers: (positive) Correspondence: Positive integers: corresponds to Prof. Busch - LSU**Example:**The set of rational numbers is countable Rational numbers: Prof. Busch - LSU**Naïve Approach**Nominator 1 Doesn’t work: we will never count numbers with nominator 2: Rational numbers: Correspondence: Positive integers: Prof. Busch - LSU**Better Approach**Prof. Busch - LSU**Rational Numbers:**Correspondence: Positive Integers: Prof. Busch - LSU**We proved:**the set of rational numbers is countable by describing an enumeration procedure (enumerator) for the correspondence to natural numbers Prof. Busch - LSU**Definition**Let be a set of strings (Language) An enumerator for is a Turing Machine that generates (prints on tape) all the strings of one by one and each string is generated in finite time Prof. Busch - LSU**strings**Enumerator Machine for output (on tape) Finite time: Prof. Busch - LSU**Enumerator Machine**Configuration Time 0 prints Time Prof. Busch - LSU**prints**Time prints Time Prof. Busch - LSU**Observation:**If for a set there is an enumerator, then the set is countable The enumerator describes the correspondence of to natural numbers Prof. Busch - LSU**Example:**The set of strings is countable Approach: We will describe an enumerator for Prof. Busch - LSU**Naive enumerator:**Produce the strings in lexicographic order: Doesn’t work: strings starting with will never be produced Prof. Busch - LSU**Proper Order**(Canonical Order) Better procedure: 1. Produce all strings of length 1 2. Produce all strings of length 2 3. Produce all strings of length 3 4. Produce all strings of length 4 .......... Prof. Busch - LSU**length 1**Produce strings in Proper Order: length 2 length 3 Prof. Busch - LSU**Proof:**Any Turing Machine can be encoded with a binary string of 0’s and 1’s Find an enumeration procedure for the set of Turing Machine strings Theorem: The set of all Turing Machines is countable Prof. Busch - LSU**Enumerator:**Repeat 1. Generate the next binary string of 0’s and 1’s in proper order 2. Check if the string describes a Turing Machine if YES: print string on output tape if NO: ignore string Prof. Busch - LSU**Binary strings**Turing Machines End of Proof Prof. Busch - LSU**Uncountable Sets**Prof. Busch - LSU**We will prove that there is a language**which is not accepted by any Turing machine Technique: Turing machines are countable Languages are uncountable (there are more languages than Turing Machines) Prof. Busch - LSU**Definition:**A set is uncountable if it is not countable We will prove that there is a language which is not accepted by any Turing machine Prof. Busch - LSU**Theorem:**If is an infinite countable set, then the powerset of is uncountable. (the powerset is the set whose elements are all possible sets made from the elements of ) Prof. Busch - LSU**Proof:**Since is countable, we can write Elements of Prof. Busch - LSU**Elements of the powerset have the form:**…… Prof. Busch - LSU**We encode each element of the powerset**with a binary string of 0’s and 1’s Powerset element Binary encoding (in arbitrary order) Prof. Busch - LSU**Observation:**Every infinite binary string corresponds to an element of the powerset: Example: Corresponds to: Prof. Busch - LSU**Let’s assume (for contradiction)**that the powerset is countable Then: we can enumerate the elements of the powerset Prof. Busch - LSU**suppose that this is the respective**Powerset element Binary encoding Prof. Busch - LSU**Take the binary string whose bits**are the complement of the diagonal Binary string: (birary complement of diagonal) Prof. Busch - LSU