1
$\begingroup$

I am reading Turing 1936 to learn about the halting problem from its origin. However, I encountered a roadblock upon reaching section four, in which Turing demonstrates that his m-configuration tables can be expressed as abbreviated "skeleton tables". I cannot wrap my head around how you are meant to use repeated substitution (as he says) to arrive at a complete m-configuration table. The first example he gives is this:

Turing 1936, Section 4, first example

I took this table and followed these instructions: "If we were to replace C throughout by q (say), B by r, and a by x, we should have a complete table for the m-configuration f (q, r, x). f is called an "m-configuration function" or "m-function"." Which had me end up with this:

My attempt at arriving at an m-configuration table

Now, all I've done is replace the variables like he explicitly said but I am unsure how to use this table compared to the previous m-configuration tables. I doubt this is correct, as I feel I am missing something big. When I see f (q, r, x), what does this mean? My understanding is something like:

  • We have function f, which takes three inputs, two being m-configurations and the third being a symbol.
  • We pass the values originally passed to function f back into f again if ə is not found, or into function f1 if ə is found. Either way the head is moved once to the left.
  • From f1 we return C if a is found under the head, if something other than a is found we pass the values back into f1 and move the head right, or if its something other than a or not a (how is this possible) then we pass the values into f2 and move the head right.
  • ...

I feel as though I am wrong in several ways and I can't find much discussion about this paper on the internet (shocker) so any help would be much appreciated! Even just seeing an expanded table could be enlightening.

$\endgroup$

1 Answer 1

1
$\begingroup$

The expression $\mathfrak{f}\,(\mathfrak{C},\mathfrak{B},a)$ is an $m$-configuration (i.e., a state), where

  • $\mathfrak{C}$ is an $m$-configuration (for example, $\mathfrak{q}$),
  • $\mathfrak{B}$ is an $m$-configuration (for example, $\mathfrak{r}$), and
  • $a$ is a tape symbol (for example, $x$).

You can read $\mathfrak{f}\,(\mathfrak{q},\mathfrak{r},x)$ as the instruction “set the machine head over the leftmost $x$ and enter $m$-configuration $\mathfrak{q}$, or if there is no $x$ on the tape, enter $m$-configuration $\mathfrak{r}$.”

How to follow this table

  1. Look up the $m$-configuration (column 1).
  2. Read the symbol under the machine head (column 2).
  3. Execute the corresponding behavior (column 3).
  4. Enter the corresponding $m$-configuration (column 4).

Example

Suppose the machine is in $m$-configuration $\mathfrak{g}$ and the machine head is at the index marked with a dot on the string below (using $\varepsilon$ because I don’t know how to type the schwa symbol): $$\varepsilon\varepsilon 0xx1x\underset{\bullet}{1}0$$ In one of the previous tables, we can define a rule like this:

$m$-config. symbol operations final $m$-config.
$\mathfrak{g}$ $1$ $L$ $\mathfrak{f}(\mathfrak{q},\mathfrak{r},x)$.

Then the machine will move left, enter the $m$-configuration $\mathfrak{f}(\mathfrak{q},\mathfrak{r},x)$ and proceed as follows:

$\varepsilon\varepsilon 0xx1\underset{\bullet}x10\quad\mathfrak{f}(\mathfrak{q},\mathfrak{r},x)$

$\varepsilon\varepsilon 0xx\underset{\bullet}1x10\quad\mathfrak{f}(\mathfrak{q},\mathfrak{r},x)$

$\varepsilon\varepsilon 0x\underset{\bullet}x1x10\quad\mathfrak{f}(\mathfrak{q},\mathfrak{r},x)$

$\varepsilon\varepsilon 0\underset{\bullet}xx1x10\quad\mathfrak{f}(\mathfrak{q},\mathfrak{r},x)$

$\varepsilon\varepsilon \underset{\bullet}0xx1x10\quad\mathfrak{f}(\mathfrak{q},\mathfrak{r},x)$

$\varepsilon\underset{\bullet}\varepsilon 0xx1x10\quad\mathfrak{f}(\mathfrak{q},\mathfrak{r},x)$

$\underset{\bullet}\varepsilon\varepsilon 0xx1x10\quad\mathfrak{f}_1(\mathfrak{q},\mathfrak{r},x)$

$\varepsilon\underset{\bullet}\varepsilon 0xx1x10\quad\mathfrak{f}_1(\mathfrak{q},\mathfrak{r},x)$

$\varepsilon\varepsilon \underset{\bullet}0xx1x10\quad\mathfrak{f}_1(\mathfrak{q},\mathfrak{r},x)$

$\varepsilon\varepsilon 0\underset{\bullet}xx1x10\quad\mathfrak{f}_1(\mathfrak{q},\mathfrak{r},x)$

$\varepsilon\varepsilon 0\underset{\bullet}xx1x10\quad\mathfrak{q}$

Of course, if no $x$ was on the tape, it would instead end up in $m$-configuration $\mathfrak{r}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.