Lab for Automated Reasoning and Analysis LARA

Differences

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

Link to this comparison view

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