3.1.7: Combining Turing Machines

Sets, Logic, Computation · LibreTexts

0%

Contents

    Text

    Size
    100%
    Theme
    Typeface
    Line length
    Spacing

    From LibreTexts, under CC BY, as the source states it; its equations are written in TeX, which the PDF shows typeset. This page at LibreTexts.

    The examples of Turing machines we have seen so far have been fairly simple in nature. But in fact, any problem that can be solved with any modern programming language can also be solved with Turing machines. To build more complex Turing machines, it is important to convince ourselves that we can combine them, so we can build machines to solve more complex problems by breaking the procedure into simpler parts. If we can find a natural way to break a complex problem down into constituent parts, we can tackle the problem in several stages, creating several simple Turing machines and combining them into one machine that can solve the problem. This point is especially important when tackling the Halting Problem in the next section.

    Example \(\PageIndex{1}\)

    Combining Machines: Design a machine that computes the function \(f(m,n) = 2(m+n)\).

    In order to build this machine, we can combine two machines we are already familiar with: the addition machine, and the doubler. We begin by drawing a state diagram for the addition machine.

    12.7.1_addition.png

    Instead of halting at state \(q_2\), we want to continue operation in order to double the output. Recall that the doubler machine erases the first stroke in the input and writes two strokes in a separate output. Let’s add an instruction to make sure the tape head is reading the first stroke of the output of the addition machine.

    12.7.2_modify.png

    It is now easy to double the input—all we have to do is connect the doubler machine onto state \(q_4\). This requires renaming the states of the doubler machine so that they start at \(q_4\) instead of \(q_0\)—this way we don’t end up with two starting states. The final diagram should look as in Figure \(\PageIndex{1}\).

    combined.png
    Figure \(\PageIndex{1}\): Combining adder and doubler machines

    This page titled 3.1.7: Combining Turing Machines was last modified on Fri, 08 Mar 2024 05:56:24 GMT and is shared under a CC BY license and was authored, remixed, and/or curated by Richard Zach et al. (Open Logic Project) .