Differences

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

--- sav08:turing_machines [2008/04/03 11:32]
vkuncak
+++ sav08:turing_machines [2008/04/03 11:45]
vkuncak
@@ Line 1: / Line 1: @@
 ====== Turing Machines ======
+(Informal reminder.)
+Turing machine has
+  * finite set of control states
+  * finite tape alphabet
+  * transition rules: in given state, when reading given symbol on tape, write given symbol and move left or right
+The language accepted by Turing machine is the set of inputs starting from which turing machine halts in an accepting state.
+On a given input machine can:
+  * halt and accept
+  * halt and reject
+  * infinitely loop
+Every well-defined procedure for computing a set of elements can be expressed using Turing machine.
+Moreover, translations from related formalisms:
+  * random-access machines
+  * recursive functions
+  * programming languages
+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$.
+Informally: an interpreter (for a sufficiently expressive programming language) cannot determine whether a given program will terminate on a given input.
 ===== References =====