• 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 Both sides previous revision Previous revision 2008/04/03 12:20 vkuncak 2008/04/03 11:45 vkuncak 2008/04/03 11:32 vkuncak 2008/04/03 11:32 vkuncak created 2008/04/03 12:20 vkuncak 2008/04/03 11:45 vkuncak 2008/04/03 11:32 vkuncak 2008/04/03 11:32 vkuncak created 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 =====