1 What the initial configuration of a Turing machine on an input string x is. 2  The fact that Turing machines can compute functions as well as decide/recognize languages. 3  The language accepted by a Turing machine (page 284). Church's Thesis: This thesis states that any algorithm can be represented as a Turing machine. 2  Universal Turing machines: A Turing machine which acts like a modern general purpose computer in that it can run other Turing machines and thus solve any problem which can be solved by Turing machines.