# Turing Machines - PowerPoint PPT Presentation  Turing Machines ## Turing Machines

##### Presentation Transcript

1. Turing Machines – Decidability Lecture 25 Section 3.1 Fri, Oct 19, 2007

2. Turing Machine as Calculator • Design a Turing Machine that will compare (<) two integers. • Input: 0110#11100 • Output: 1 (true) • Input: 11100#0110 • Output: 0 (false)

3. Turing Machine as Calculator • Design a Turing Machine that will add two integers. • Input: 0110#11100 • Output: 100010

4. Turing Machine as Calculator • Design a Turing Machine that will multiply two integers. • Input: 0110#11100 • Output: 10101000

5. Turing Machine as Calculator • Design a Turing Machine that will find the square root of an integer. • Input: 11100 • Output: 101

6. Configurations • The current “state” of a Turing machine is fully described by specifying • The current state, • The current tape position, • The current tape contents.

7. Configurations • This can be summarized in a triple uqv, called a configuration, where u, v * and qQ. • The interpretation is • The current state is q. • The current tape content is uv. • The current tape position is at the first symbol in v.

8. Computations • We say that a configuration C1yields a configuration C2 if there is a transition that takes the Turing machine from C1 to C2. • A computation is a sequence of configurations C1, …, Cn, where Ci yields Ci + 1 for i = 1, …, n – 1.

9. Example • Our machine that accepts {w#w} will perform the following computation on input 101#101: • q0101#101 • \$q301#101 • \$0q31#101 • \$01q3#101 • \$01#q4101

10. Example • \$01q5#\$01 • \$0q61#\$01 • \$q601#\$01 • q6\$01#\$01 • \$q001#\$01 • \$\$q11#\$01 • etc.

11. Accepting and Rejecting Configurations • The start configuration on input w is q0w. • An accepting configuration is one where the state is qaccept. • A rejecting configuration is one where the state is qreject.

12. Accepting Input • A Turing Machine accepts input w if there is a computation C1, …, Cn, where • C1 is the start configuration on w. • Cn is an accepting configuration.

13. Rejecting Input • A Turing Machine rejects input w if there is a computation C1, …, Cn, where • C1 is the start configuration on w. • Cn is a rejecting configuration.

14. The Third Possibility • It is possible that a Turing Machine neither accepts nor rejects an input w.

15. Turing-Recognizable Languages • The language of a Turing machineM is the set of input strings that are accepted by M. L(M) = {w | M accepts w}. • A language is Turing-recognizable if it is accepted by some Turing machine.

16. Turing-Decidable Languages • A Turing Machine is a decider if it halts on all inputs. • A Turing machine Mdecides a language L if M accepts every string in L and rejects every string not in L. • A language is Turing-decidable if it is decided by some Turing machine.

17. Example • The language {w#w | w *} is a Turing-decidable language. • Every Turing-decidable language is Turing-recognizable, but not every Turing-recognizable language is Turing-decidable.