Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision | ||
sav08:turing_machines [2008/04/03 11:32] vkuncak |
sav08:turing_machines [2008/04/03 12:20] (current) vkuncak |
||
---|---|---|---|
Line 1: | Line 1: | ||
====== Turing Machines ====== | ====== Turing Machines ====== | ||
+ | (Informal reminder.) | ||
+ | |||
+ | Turing machine has | ||
+ | * finite set of control states | ||
+ | * finite tape alphabet | ||
+ | * transition rules: in given state, when reading given symbol on tape, write given symbol and move left or right | ||
+ | |||
+ | The language accepted by Turing machine is the set of inputs starting from which turing machine halts in an accepting state. | ||
+ | |||
+ | On a given input machine can: | ||
+ | * halt and accept | ||
+ | * halt and reject | ||
+ | * infinitely loop | ||
+ | |||
+ | Every well-defined procedure for computing a set of elements can be expressed using Turing machine. | ||
+ | |||
+ | Moreover, translations from related formalisms: | ||
+ | * random-access machines | ||
+ | * recursive functions | ||
+ | * programming languages | ||
+ | |||
+ | There exists an algorithm = There exists a Turing machine | ||
+ | |||
+ | **Theorem:** There is no algorithm for deciding, given a description of a Turing machine $M$, and an input $w$ to the Turing machine, whether $M$ accepts $w$. | ||
+ | |||
+ | Informally: an interpreter (for a sufficiently expressive programming language) cannot determine whether a given program will terminate and give a positive answer on a given input. | ||
+ | |||
+ | By Theorem and definition of "$M$ accepts $w$", there is no algorithm for checking whether there exists a **Turing machine computation history** that is, a finite sequence of Turing machine configurations from the initial state to an accepting state. | ||
===== References ===== | ===== References ===== |