class: middle, center, title-slide count: false
A Turing machine example
Gilles Louppe
g.louppe@uliege.be
class: middle
class: middle
.center.circle[
]
A Turing machine is a mathematical model of computation that defines an abstract machine, which manipulates symbols on a strip of tape according to a table of rules.
Despite the model's simplicity, given any computer algorithm, a Turing machine capable of simulating that algorithm's logic can be constructed.
class: middle, center
.width-100[
]
Following Hopcroft and Ullman (1979, p. 148), a (one-tape) Turing machine can be formally defined as a 7-tuple
-
$Q$ is a finite, non-empty set of states; -
$\Gamma$ is a finite, non-empty set of tapes alphabet symbols; -
$b \in \Gamma \setminus \{b\}$ is the set of input symbols, that is, the set of symbols allowed to appear in the initial tape contents; -
$q_0 \in Q$ is the initial state; -
$F \subseteq Q$ is the set of final states or accepting states. The initial tape contents is said to be accepted by$M$ if it eventually halts in a state from$F$ . -
$\delta: (Q \setminus F) \times \Gamma \rightarrow Q \times \Gamma \times \{L,R\}$ is the state transition function.
class: middle
Lorem ipsum.
.footnote[This is a footnote.]
class: middle
class: middle
- abc
- def
- ghi
- Turing, Alan M. "Computing machinery and intelligence." Parsing the Turing Test. Springer, Dordrecht, 2009. 23-65.
class: end-slide, center count: false
The end.