- English only

# Lab for Automated Reasoning and Analysis LARA

# Differences

This shows you the differences between two versions of the page.

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 ===== |