L14

Information about L14

Published on January 5, 2008

Author: Sevastian

Source: authorstream.com

Content

Turing Machines:  Turing Machines Zeph Grunschlag Agenda:  Agenda Turing Machines Alan Turing Motivation Church-Turing Thesis Definitions Computation TM Configuration Recognizers vs. Deciders Alan Turing:  Alan Turing Alan Turing was one of the founding fathers of CS. His computer model –the Turing Machine– was inspiration/premonition of the electronic computer that came two decades later Was instrumental in cracking the Nazi Enigma cryptosystem in WWII Invented the “Turing Test” used in AI Legacy: The Turing Award. Pre-eminent award in Theoretical CS A Thinking Machine:  A Thinking Machine First Goal of Turing’s Machine: A model that can compute anything that a human can compute. Before invention of electronic computers the term “computer” actually referred to a person who’s line of work is to calculate numerical quantities! As this is a philosophical endeavor, it can’t really be proved. Turing’s Thesis: Any “algorithm” can be carried out by one of his machines A Thinking Machine:  A Thinking Machine Second Goal of Turing’s Machine: A model that’s so simple, that can actually prove interesting epistemological results. Eyed Hilbert’s 10th problem, as well as a computational analog of Gödel’s Incompleteness Theorem in Logic. Philosophy notwithstanding, Turing’s programs for cracking the Enigma cryptosystem prove that he really was a true hacker! Turing’s machine is actually easily programmable, if you really get into it. Not practically useful, though… A Thinking Machine:  A Thinking Machine Imagine a super-organized, obsessive-compulsive human computer. The computer wants to avoid mistakes so everything written down is completely specified one letter/number at a time. The computer follows a finite set of rules which are referred to every time another symbol is written down. Rules are such that at any given time, only one rule is active so no ambiguity can arise. Each rule activates another rule depending on what letter/number is currently read, EG: A Thinking Machine EG Successor Program:  A Thinking Machine EG Successor Program Sample Rules: If read 1, write 0, go right, repeat. If read 0, write 1, HALT! If read , write 1, HALT! Let’s see how they are carried out on a piece of paper that contains the reverse binary representation of 47: A Thinking Machine EG Successor Program:  A Thinking Machine EG Successor Program If read 1, write 0, go right, repeat. If read 0, write 1, HALT! If read , write 1, HALT! A Thinking Machine EG Successor Program:  A Thinking Machine EG Successor Program If read 1, write 0, go right, repeat. If read 0, write 1, HALT! If read , write 1, HALT! A Thinking Machine EG Successor Program:  A Thinking Machine EG Successor Program If read 1, write 0, go right, repeat. If read 0, write 1, HALT! If read , write 1, HALT! A Thinking Machine EG Successor Program:  A Thinking Machine EG Successor Program If read 1, write 0, go right, repeat. If read 0, write 1, HALT! If read , write 1, HALT! A Thinking Machine EG Successor Program:  A Thinking Machine EG Successor Program If read 1, write 0, go right, repeat. If read 0, write 1, HALT! If read , write 1, HALT! A Thinking Machine EG Successor Program:  A Thinking Machine EG Successor Program If read 1, write 0, go right, repeat. If read 0, write 1, HALT! If read , write 1, HALT! A Thinking Machine EG Successor Program:  A Thinking Machine EG Successor Program So the successor’s output on 111101 was 000011 which is the reverse binary representation of 48. Similarly, the successor of 127 should be 128: A Thinking Machine EG Successor Program:  A Thinking Machine EG Successor Program If read 1, write 0, go right, repeat. If read 0, write 1, HALT! If read , write 1, HALT! A Thinking Machine EG Successor Program:  A Thinking Machine EG Successor Program If read 1, write 0, go right, repeat. If read 0, write 1, HALT! If read , write 1, HALT! A Thinking Machine EG Successor Program:  A Thinking Machine EG Successor Program If read 1, write 0, go right, repeat. If read 0, write 1, HALT! If read , write 1, HALT! A Thinking Machine EG Successor Program:  A Thinking Machine EG Successor Program If read 1, write 0, go right, repeat. If read 0, write 1, HALT! If read , write 1, HALT! A Thinking Machine EG Successor Program:  A Thinking Machine EG Successor Program If read 1, write 0, go right, repeat. If read 0, write 1, HALT! If read , write 1, HALT! A Thinking Machine EG Successor Program:  A Thinking Machine EG Successor Program If read 1, write 0, go right, repeat. If read 0, write 1, HALT! If read , write 1, HALT! A Thinking Machine EG Successor Program:  A Thinking Machine EG Successor Program If read 1, write 0, go right, repeat. If read 0, write 1, HALT! If read , write 1, HALT! A Thinking Machine EG Successor Program:  A Thinking Machine EG Successor Program If read 1, write 0, go right, repeat. If read 0, write 1, HALT! If read , write 1, HALT! A Thinking Machine EG Successor Program:  A Thinking Machine EG Successor Program If read 1, write 0, go right, repeat. If read 0, write 1, HALT! If read , write 1, HALT! A Thinking Machine:  A Thinking Machine It was hard for the ancients to believe that any algorithm could be carried out on such a device. For us, it’s much easier to believe, especially if you’ve programmed in assembly! However, ancients did finally believe Turing when Church’s lambda-calculus paradigm (on which lisp programming is based) proved equivalent! Turing Machines:  Turing Machines A Turing Machine (TM) is a device with a finite amount of read-only “hard” memory (states), and an unbounded1 amount of read/write tape-memory. There is no separate input. Rather, the input is assumed to reside on the tape at the time when the TM starts running. Just as with Automata, TM’s can either be input/output machines (compare with Finite State Transducers), or yes/no decision machines. Start with yes/no machines. Comparison with Previous Models:  Comparison with Previous Models Comparison with Previous Models:  Comparison with Previous Models Comparison with Previous Models:  Comparison with Previous Models Comparison with Previous Models:  Comparison with Previous Models Turing Machine Decision Machine Example:  Turing Machine Decision Machine Example First example (adding 1 bit to reverse binary string) was basically something that a Finite Transducer could have achieved (except when there’s overflow). Let’s give an example from next step up in language hierarchy. {bit-strings with same number of 0’s as 1’s} –a context free language: Turing Machine Decision Machine Example:  Turing Machine Decision Machine Example This is a “true” Turing machine as: Tape is semi-infinite (indicated by torn cell): Input is prepared at beginning of tape No intrinsic way to detect left tape end similar to empty stack detection problem for PDA’s similar trick used –introduce $ as the end symbol All rules must include a move direction (R/L) Situations that can’t happen aren’t dealt with (technically under-deterministic) Turing Machine Decision Machine Example:  Turing Machine Decision Machine Example {bit-strings with same number of 0’s as 1’s}: Pseudocode: while (there is a 0 and a 1) cross these out if (everything crossed out) accept else reject TM Example Instructions Set:  TM Example Instructions Set 0. if read , go right (dummy move), ACCEPT if read 0, write $, go right, goto 1 // $ detects start of tape if read 1, write $, go right, goto 2 1. if read , go right, REJECT if read 0 or X, go right, repeat (= goto 1) // look for a 1 if read 1, write X, go left, goto 3 2. if read , go right, REJECT if read 1 or X, go right, repeat // look for a 0 if read 0, write X, go left, goto 3 3. if read $, go right, goto 4 // look for start of tape else, go left, repeat 4. if read 0, write X, go right, goto 1 // similar to step 0 if read 1, write X, go right, goto 2 if read X, go right, repeat if read , go right, ACCEPT TM Example State Diagram:  TM Example State Diagram These instructions can be expressed by a familiar looking flow diagram: 0 1 rej 0$,R acc R 2 1$,R 0|XR 1|XR 3 R 0X,L 1X,L 0|1|XL 4 $R XR 0X,R 1X,R R TM Transition Notation:  TM Transition Notation An edge from the state p to the state q labeled by … ab,D means if in state p and tape head reading a, replace a by b and move in the direction D, and into state q aD means if in state p and tape head reading a, don’t change a and move in the direction D, and into state q a|b|…|z  … means that given that the tape head is reading any of the pipe separated symbols, take same action on any of the symbols TM Configuration Notation:  TM Configuration Notation A TM’s next action is completely determined by current state and symbol read, so can predict all of future actions if know: current state current tape contents current position of TM’s reading “head” Handy notation lists all of these in a single string. A symbol representing current state, is sandwiched between content of tape to left of head, and content of tape to right (including tape head). The part of tape which is blank ad-infinitum is ignored. TM Configuration Notation:  TM Configuration Notation For example Is denoted by: $xxx1q3010 Reading rule 3 TM Example Crazy Web-Page:  TM Example Crazy Web-Page The following link shows how the example machine accepts 01101010 and how the tape configuration notation changes step by step. TM Formal Definition Static Picture:  TM Formal Definition Static Picture DEF: A Turing machine (TM) consists of a 7-tuple M = (Q, S, G, d, q0, qacc, qrej). Q, S, and q0, are the same as for an FA. G is the tape alphabet which necessarily contains the blank symbol , as well as the input alphabet S. d is as follows: Therefore given a non-halt state p, and a tape symbol x, d(p,x) = (q,y,D) means that TM goes into state q, replaces x by y, and the tape head moves in direction D. TM Dynamic Picture:  TM Dynamic Picture A string x is accepted by M if after being put on the tape with the Turing machine head set to the left-most position, and letting M run, M eventually enters the accept state.  In this case w is an element of L(M) –the language accepted by M. We can formalize this notion as follows: TM Formal Definition Dynamic Picture:  TM Formal Definition Dynamic Picture Suppose TM’s configuration at time t is given by uapxv where p is the current state, ua is what’s to the left of the head, x is what’s being read, and v is what’s to the right of the head. If d(p,x) = (q,y,R) then write: uapxv  uaypv With resulting configuration uaypv at time t+1. If, d(p,x) = (q,y,L) instead, then write: uapxv  upayv There are also two special cases: head is forging new ground –pad with the blank symbol  head is stuck at left end –by def. head stays put (only case) “” is read as “yields” TM Formal Definition Dynamic Picture:  TM Formal Definition Dynamic Picture As with context free grammars, one can consider the reflexive, transitive closure “*” of “”. I.e. this is the relation between strings recursively defined by: if u = v then u * v if u v then u * v if u *v and v * w, then u *w “*” is read as “computes to” A string x is said to be accepted by M if the start configuration q0 x computes to some accepting configuration y –i.e., a configuration containing qacc. The language accepted by M is the set of all accepted strings. I.e: L(M) = { x  S* |  accepting config. y, q0 x * y } TM Acceptors vs. Deciders:  TM Acceptors vs. Deciders Three possibilities occur on a given input w : The TM M eventually enters qacc and therefore halts and accepts. (w  L(M) ) The TM M eventually enters qrej or crashes somewhere. M rejects w . (w  L(M) ) Neither occurs! I.e., M never halts its computation and is caught up in an infinite loop, never reaching qacc or qrej.  In this case w is neither accepted nor rejected. However, any string not explicitly accepted is considered to be outside the accepted language. (w  L(M) ) TM Acceptors vs. Deciders:  TM Acceptors vs. Deciders Any Turing Machines is said to be a recognizer and recognizes L(M); if in addition, M never enters an infinite loop, M is called a decider and is said to decide L(M). Q: Is the above M an recognizer? A decider? What is L(M)? 0 1 rej acc 2 R 1R 0R 1R 0R 0R 1L TM Acceptors vs. Deciders:  TM Acceptors vs. Deciders A: M is an recognizer but not a decider because 101 causes an infinite loop. L(M) = 1+ 0+ Q: Is L(M ) decidable ? 0 1 rej acc 2 R 1R 0R 1R 0R 0R 1L TM Acceptors vs. Deciders:  TM Acceptors vs. Deciders A: Yes. All regular languages are decidable because can always convert a DFA into a TM without infinite loops. Constructive Example:  Constructive Example Here’s a document showing how modular design can help you write down a TM decider for {anbncn}. The example is non-context free.

Related presentations


Other presentations created by Sevastian

ISPS
05. 11. 2007
0 views

ISPS

Love and Friendship
24. 12. 2007
0 views

Love and Friendship

The Meiji Restoration
27. 03. 2008
0 views

The Meiji Restoration

Passover Communion 2007
05. 03. 2008
0 views

Passover Communion 2007

frbr2
27. 02. 2008
0 views

frbr2

BB 3 06 presGC
07. 01. 2008
0 views

BB 3 06 presGC

Cambodia
07. 01. 2008
0 views

Cambodia

GEGPresentation
04. 01. 2008
0 views

GEGPresentation

Week4b
27. 09. 2007
0 views

Week4b

The Persian Wars
07. 12. 2007
0 views

The Persian Wars

4TTExcav2
10. 12. 2007
0 views

4TTExcav2

Hooters ppt Recovered
12. 12. 2007
0 views

Hooters ppt Recovered

anzio
30. 10. 2007
0 views

anzio

Wright ppt
31. 10. 2007
0 views

Wright ppt

new sol vocab review mouse
01. 11. 2007
0 views

new sol vocab review mouse

aspects culturel sdela France
02. 11. 2007
0 views

aspects culturel sdela France

Proctor BAT Brief
05. 11. 2007
0 views

Proctor BAT Brief

Area Communication Systems
06. 11. 2007
0 views

Area Communication Systems

Chapter4
07. 11. 2007
0 views

Chapter4

laburinary 03
13. 11. 2007
0 views

laburinary 03

Volkswagen Aids Care Program
16. 11. 2007
0 views

Volkswagen Aids Care Program

eurotb slides balkans
21. 11. 2007
0 views

eurotb slides balkans

Baseline project Summer 2007
04. 12. 2007
0 views

Baseline project Summer 2007

PressPack
23. 11. 2007
0 views

PressPack

Kids Help Phone Presentation
23. 12. 2007
0 views

Kids Help Phone Presentation

drawinglessons
02. 01. 2008
0 views

drawinglessons

1 OpenPresentation
28. 09. 2007
0 views

1 OpenPresentation

Vasa
07. 11. 2007
0 views

Vasa

11 tg
04. 01. 2008
0 views

11 tg

paper8
26. 11. 2007
0 views

paper8

Transits of Venus Pictures Only
26. 10. 2007
0 views

Transits of Venus Pictures Only

3 ModelagemEstatistica
28. 12. 2007
0 views

3 ModelagemEstatistica

Conway 2
24. 10. 2007
0 views

Conway 2

mln
18. 12. 2007
0 views

mln

JangWoo Son
09. 10. 2007
0 views

JangWoo Son

001
31. 10. 2007
0 views

001

sunum tasarim
14. 11. 2007
0 views

sunum tasarim

Spinoffs
25. 10. 2007
0 views

Spinoffs

Joao Castro
28. 11. 2007
0 views

Joao Castro

TS107 WEEK4 2 TRANSPORT
12. 11. 2007
0 views

TS107 WEEK4 2 TRANSPORT

7 Dividing Fractions
28. 12. 2007
0 views

7 Dividing Fractions

Module 2 VOCs
08. 11. 2007
0 views

Module 2 VOCs

Internet Detective LILAC2006
13. 12. 2007
0 views

Internet Detective LILAC2006

smn presentation
06. 11. 2007
0 views

smn presentation

ULSDDowngrading
06. 11. 2007
0 views

ULSDDowngrading

maslennikov2
01. 11. 2007
0 views

maslennikov2

mobicom1
31. 10. 2007
0 views

mobicom1

SACS WorkshopJuly2007
22. 11. 2007
0 views

SACS WorkshopJuly2007