Lab for Automated Reasoning and Analysis LARA

Differences

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

Link to this comparison view

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 =====
 
sav08/turing_machines.txt · Last modified: 2008/04/03 12:20 by vkuncak
 
© EPFL 2018 - Legal notice