• English only

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