Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision | |||
sav08:turing_machines [2008/04/03 11:45] vkuncak |
sav08:turing_machines [2008/04/03 12:20] (current) vkuncak |
||
---|---|---|---|
Line 24: | Line 24: | ||
There exists an algorithm = There exists a Turing machine | 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$ will halt on $w$. | + | **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 on a given input. | + | 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 ===== |