Can one capture the properties of Turing machine using only function definitions?

71 Views Asked by At

I am trying to capture the definition of Turing machines as abstractly as possible (without any implementation). Will a definition like this do the trick?


Definition [Turing machine]:

Let $\mathbb{L}$ be the set of all finite sentences with finite alphabet $\Sigma$ including the empty sentence $\varnothing$. As an example, the sentences of the binary alphabet $\Sigma=\{0,1 \}$ are the binary sentences.

A Turing machine is a partial function $\operatorname{TM}: \mathbb{L} \to \mathbb{L}$:

$$ \operatorname{TM}(d) = r $$

iff $\operatorname{TM}(d)$ halts.


Does this definition capture all Turing machines and only Turing machines?

1

There are 1 best solutions below

2
On

There are more partial functions from $\mathbb{L}$ to $\mathbb{L}$ than there are Turing machines in the classical sense of the term. Specifically, there are at least $2^{\aleph_0}$ partial functions from $\mathbb{L}$ to $\mathbb{L}$ (this counts the number of mappings from binary sequences to the singleton sequences $\mathtt{0}$ and $\mathtt{1}$), but there are only $\aleph_0$ possible TMs (each TM can be written as a binary sequence).

Since your definition includes at least $2^{\aleph_0}$ items but there are only $\aleph_0$ Turing machines, your definition can't be capturing all and only the Turing machines.

An example of something not captured: pick any non-recursively-enumerable language (say, the language of all TMs that don't accept their own encodings). Then you can define a (total) function $f : \mathbb{L} \to \mathbb{L}$ as

$$f(d) = \begin{cases} \mathbb{0} & \text{if }d \text{ is the encoding of a TM that does not accept itself } \\ \mathbb{1} & \text{otherwise} \end{cases}$$

No TM exists that (semi)-decides this set, but by your definition this object $f$ would be a Turing machine.

But more generally to your original question - can you capture Turing machines just using functions? - the answer is yes. The $\mu$-recursive functions are a family of recursively-defined (partial) functions that compute exactly the same set as Turing machines. For a slightly more general notion of what a "function" is, you could look to the $\lambda$-calculus, which similarly captures the expressive power of Turing machines using a system based purely on recursive application of functions.