Turing Machines - PowerPoint PPT Presentation

turing machines decidability n.
Skip this Video
Loading SlideShow in 5 Seconds..
Turing Machines PowerPoint Presentation
Turing Machines

play fullscreen
1 / 17
Download Presentation
Views
Download Presentation

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.