<p>The expression <span class="math-container">$\mathfrak{f}\,(\mathfrak{C},\mathfrak{B},a)$</span> is an <span class="math-container">$m$</span>-configuration (i.e., a state), where</p>
<ul>
<li><span class="math-container">$\mathfrak{C}$</span> is an <span class="math-container">$m$</span>-configuration (for example, <span class="math-container">$\mathfrak{q}$</span>),</li>
<li><span class="math-container">$\mathfrak{B}$</span> is an <span class="math-container">$m$</span>-configuration (for example, <span class="math-container">$\mathfrak{r}$</span>), and</li>
<li><span class="math-container">$a$</span> is a tape symbol (for example, <span class="math-container">$x$</span>).</li>
</ul>
<p>You can read <span class="math-container">$\mathfrak{f}\,(\mathfrak{q},\mathfrak{r},x)$</span> as the instruction “set the machine head over the leftmost <span class="math-container">$x$</span> and enter <span class="math-container">$m$</span>-configuration <span class="math-container">$\mathfrak{q}$</span>, or if there is no <span class="math-container">$x$</span> on the tape, enter <span class="math-container">$m$</span>-configuration <span class="math-container">$\mathfrak{r}$</span>.”</p>
<h3>How to follow this table</h3>
<ol>
<li>Look up the <span class="math-container">$m$</span>-configuration (column 1).</li>
<li>Read the symbol under the machine head (column 2).</li>
<li>Execute the corresponding behavior (column 3).</li>
<li>Enter the corresponding <span class="math-container">$m$</span>-configuration (column 4).</li>
</ol>
<h3>Example</h3>
<p>Suppose the machine is in <span class="math-container">$m$</span>-configuration <span class="math-container">$\mathfrak{g}$</span> and the machine head is at the index marked with a dot on the string below (using <span class="math-container">$\varepsilon$</span> because I don’t know how to type the schwa symbol):
<span class="math-container">$$\varepsilon\varepsilon 0xx1x\underset{\bullet}{1}0$$</span>
In one of the <em>previous</em> tables, we can define a rule like this:</p>
<div class="s-table-container"><table class="s-table">
<thead>
<tr>
<th><em><span class="math-container">$m$</span>-config.</em></th>
<th><em>symbol</em></th>
<th><em>operations</em></th>
<th><em>final <span class="math-container">$m$</span>-config.</em></th>
</tr>
</thead>
<tbody>
<tr>
<td><span class="math-container">$\mathfrak{g}$</span></td>
<td><span class="math-container">$1$</span></td>
<td><span class="math-container">$L$</span></td>
<td><span class="math-container">$\mathfrak{f}(\mathfrak{q},\mathfrak{r},x)$</span>.</td>
</tr>
</tbody>
</table></div>
<p>Then the machine will move left, enter the <span class="math-container">$m$</span>-configuration <span class="math-container">$\mathfrak{f}(\mathfrak{q},\mathfrak{r},x)$</span> and proceed as follows:</p>
<p><span class="math-container">$\varepsilon\varepsilon 0xx1\underset{\bullet}x10\quad\mathfrak{f}(\mathfrak{q},\mathfrak{r},x)$</span></p>
<p><span class="math-container">$\varepsilon\varepsilon 0xx\underset{\bullet}1x10\quad\mathfrak{f}(\mathfrak{q},\mathfrak{r},x)$</span></p>
<p><span class="math-container">$\varepsilon\varepsilon 0x\underset{\bullet}x1x10\quad\mathfrak{f}(\mathfrak{q},\mathfrak{r},x)$</span></p>
<p><span class="math-container">$\varepsilon\varepsilon 0\underset{\bullet}xx1x10\quad\mathfrak{f}(\mathfrak{q},\mathfrak{r},x)$</span></p>
<p><span class="math-container">$\varepsilon\varepsilon \underset{\bullet}0xx1x10\quad\mathfrak{f}(\mathfrak{q},\mathfrak{r},x)$</span></p>
<p><span class="math-container">$\varepsilon\underset{\bullet}\varepsilon 0xx1x10\quad\mathfrak{f}(\mathfrak{q},\mathfrak{r},x)$</span></p>
<p><span class="math-container">$\underset{\bullet}\varepsilon\varepsilon 0xx1x10\quad\mathfrak{f}_1(\mathfrak{q},\mathfrak{r},x)$</span></p>
<p><span class="math-container">$\varepsilon\underset{\bullet}\varepsilon 0xx1x10\quad\mathfrak{f}_1(\mathfrak{q},\mathfrak{r},x)$</span></p>
<p><span class="math-container">$\varepsilon\varepsilon \underset{\bullet}0xx1x10\quad\mathfrak{f}_1(\mathfrak{q},\mathfrak{r},x)$</span></p>
<p><span class="math-container">$\varepsilon\varepsilon 0\underset{\bullet}xx1x10\quad\mathfrak{f}_1(\mathfrak{q},\mathfrak{r},x)$</span></p>
<p><span class="math-container">$\varepsilon\varepsilon 0\underset{\bullet}xx1x10\quad\mathfrak{q}$</span></p>
<p>Of course, if no <span class="math-container">$x$</span> was on the tape, it would instead end up in <span class="math-container">$m$</span>-configuration <span class="math-container">$\mathfrak{r}$</span>.</p>

CC BY-SA 4.0
2024-05-01T18:50:22.313Z
2024-05-01T18:50:22.313Z
wobtax
<p>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 <em>m</em>-configuration tables can be expressed as abbreviated &quot;skeleton tables&quot;. I cannot wrap my head around how you are meant to use repeated substitution (as he says) to arrive at a complete <em>m</em>-configuration table. The first example he gives is this:</p>
<p><a href="https://i.sstatic.net/nfUjd.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/nfUjd.png" alt="Turing 1936, Section 4, first example" /></a></p>
<p>I took this table and followed these instructions: <em>&quot;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 &quot;m-configuration function&quot; or &quot;m-function&quot;.&quot;</em> Which had me end up with this:</p>
<p><a href="https://i.sstatic.net/LZuqK.jpg" rel="nofollow noreferrer"><img src="https://i.sstatic.net/LZuqK.jpg" alt="My attempt at arriving at an m-configuration table" /></a></p>
<p>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 <em>m</em>-configuration tables. I doubt this is correct, as I feel I am missing something big. When I see <em>f (q, r, x)</em>, what does this mean? My understanding is something like:</p>
<ul>
<li>We have function <em>f</em>, which takes three inputs, two being <em>m</em>-configurations and the third being a symbol.</li>
<li>We pass the values originally passed to function <em>f</em> back into <em>f</em> again if <strong>ə</strong> is not found, or into function <em>f<sub>1</sub></em> if <strong>ə</strong> is found. Either way the head is moved once to the left.</li>
<li>From <em>f<sub>1</sub></em> we return <em><strong>C</strong></em> if <strong>a</strong> is found under the head, if something other than <strong>a</strong> is found we pass the values back into <em>f<sub>1</sub></em> and move the head right, or if its something other than <strong>a</strong> or <strong>not a</strong> (how is this possible) then we pass the values into <em>f<sub>2</sub></em> and move the head right.</li>
<li>...</li>
</ul>
<p>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.</p>

<turing-machines><function>
Turing 1936 Skeleton Tables Procedure
Missingno
# Turing 1936 Skeleton Tables Procedure

(Asked by: username_0 on 2024-04-18)

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](https://i.sstatic.net/nfUjd.png)](https://i.sstatic.net/nfUjd.png)

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](https://i.sstatic.net/LZuqK.jpg)](https://i.sstatic.net/LZuqK.jpg)

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.

**Tags:** turing-machines, function

---

## 1 answers

### Answer by username_1 on 2024-05-01. Score: 1

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}$.


---

