28-11-2012, 05:39 PM
Turing Machines
1Turing Machines.ppt (Size: 251 KB / Downloads: 24)
The most powerful automata (> FAs and PDAs )
invented by Turing in 1936
can compute any function normally considered computable
Turing-Church Theses:
Anything (function, problem, set etc.) that is (though to be) computable is computable by a Turing machine (i.e., Turing-computable).
Other equivalent formalisms:
post systems (string rewriting system)
PSG (phrase structure grammars) : on strings
m-recursive function : on numbers
l-calculus, combinatory logic: on l-term
C, BASIC, PASCAL, JAVA languages,… : on strings
Informal description of a Turing machine
1. Finite automata (DFAs, NFAs, etc.):
limited input tape: one-way, read-only
no working-memory
finite-control store (program)
2. PDAs:
limited input tape: one-way, read-only
one additional stack as working memory
finite-control store (program)
3. Turing machines (TMs):
a semi-infinite tape storing input and supplying additional working storage.
finite control store (program)
can read/write and two-way(move left and right) depending on the program state and input symbol scanned.