Turing Machine Design for Function Computation

1. Turing Machines as Function Computers

A Turing Machine computes a function $f:{\Sigma }^{\ast }\to {\Gamma }^{\ast }$ if, for any input string $w\in {\Sigma }^{\ast }$, the TM, when started in the configuration $q_{0}w$, halts in a configuration where $f(w)$ is the only content on the tape. The computation looks like this:

where $q_f$ is a halting state. The content $f(w)$ on the tape is the result of the computation.

For arithmetic functions, it's often easiest to work with a unary number system. In unary, a number $n$ is represented by a string of $n$ identical symbols. For example, using 1 as our symbol:

• 1 represents the number 1
• 111 represents the number 3
• The empty string, $ϵ$, represents 0

Let's dive into designing TMs for some fundamental functions.

2. Basic Unary Arithmetic: Increment and Decrement

The simplest functions are increment ($f(x)=x+1$) and decrement ($f(x)=x-1$). The logic for these is very straightforward.

Incrementing a Unary Number

Strategy: To add 1 to a number represented in unary, we just need to add one more 1 to the string.

1. Start at the beginning of the input string.
2. Scan right across all the 1s.
3. When the first blank symbol (⊔) is found, replace it with a 1.
4. Halt.

Decrementing a Unary Number

Strategy: To subtract 1, we need to remove one 1 from the string.

1. Start at the beginning of the input string.
2. Scan right across all the 1s.
3. When the first blank symbol (⊔) is found, move one step to the left.
4. Replace the rightmost 1 with a blank symbol.
5. Halt.

The following video provides a clear walkthrough of how to translate these simple strategies into TM transition diagrams.

3. String Manipulation: Copying a String

A more complex and essential function is string copying: $f(w)=w\#w$, where # is a separator. For example, if the input is 010, the output should be 010#010.

This task requires the TM to "remember" symbols from the original string while writing them to a new location. This is a perfect application of the "marking" and "zigzag" strategy we used in the previous lesson.

Strategy:

1. Setup: Scan to the end of the input string $w$ and write the separator #. Rewind to the beginning.
2. Main Loop:
   a. Find the first unmarked symbol in $w$ (e.g., the leftmost 0 or 1).
   b. "Mark" it to remember which symbol it is and to know it's being processed. A common technique is to use different symbols from the tape alphabet (e.g., change 0 to A, 1 to B).
   c. Scan right, past the rest of $w$ and the separator #, to the end of the tape.
   d. Write the symbol you are copying (0 or 1).
   e. Rewind left, back to the marked symbol (A or B).
   f. "Unmark" the symbol (change A back to 0, B back to 1) and move one step right to begin the next iteration of the loop.
3. Termination: The loop ends when, at the beginning of an iteration, the machine sees the # separator instead of a 0 or 1. This means all of $w$ has been copied. The machine can then clean up the tape if necessary and halt.

This process is more involved, so a detailed walkthrough is very helpful.

This copy operation highlights the core capabilities of a TM: using its states as short-term memory, modifying the tape to keep track of progress, and moving freely back and forth across the work area.

4. Back to Arithmetic: Unary Addition

Now let's design a TM to compute the sum of two unary numbers, $f(m,n)=m+n$. The input will be formatted as 1...1#1...1, where there are $m$ ones, a separator, and $n$ ones. The output should be a single string of $m+n$ ones.

Example: Input 11#111 (for 2+3). Output should be 11111 (for 5).

Strategy: The key insight is that we can merge the two strings of ones.

1. Scan right until the # separator is found.
2. Change the # into a 1. The tape now holds a single string of $m+1+n$ ones.
3. To get the correct sum of $m+n$, we need to remove one 1. Scan all the way to the right end of the newly formed string.
4. When the first blank is found, move one step left.
5. Erase the last 1 by replacing it with a blank.
6. Halt.

This visual demonstration will clarify the process.

Here is a state diagram that implements a similar logic for unary addition.

Conclusion

In this lesson, we've seen that Turing Machines are not just verifiers but powerful calculators. By manipulating symbols on their tape, they can compute a wide range of functions, from simple arithmetic to complex string operations.

Key Takeaways:

• A TM computes a function by transforming its initial tape content ($w$) into a final tape content ($f(w)$) upon halting.
• The choice of data representation (like unary vs. binary) can significantly impact the complexity of the TM design.
• Simple functions like unary increment/decrement require simple, linear passes over the tape.
• More complex functions like string copying require "memory" techniques like marking symbols and using the "zigzag" scanning pattern.
• Your experience with designing algorithms is directly applicable here. Breaking down a function into a sequence of simple, mechanical steps is the key to designing a TM.
• Just as in software engineering, complex TMs can be designed in a modular way. The document "Turing Machines - More Examples" (resource LINK) shows how a binary ADD machine can be built using INCR (increment) and DECR (decrement) as subroutines.

Preview of the Next Lesson:
Designing the string copy TM with a single tape felt a bit cumbersome, didn't it? It required a lot of back-and-forth movement. What if we had more than one tape? In our next lesson, we will explore variations of the Turing Machine, such as multi-tape TMs, and prove that these more convenient models are computationally equivalent to the standard, single-tape TM we've been using.