Question

Suppose we already have Turing machine instructions to copy a unary string; we also know how to add two unary numbers. Describe (in words only) the design of a Turing machine to multiply two unary numbers.

Short answer

Multiply unary numbers by repeated addition using a Turing machine loop.

Step-by-step solution

Understanding Unary Numbers

Unary number representation involves representing a natural number as a sequence of identical symbols. For instance, the unary representation of the number 3 is '111'.

Define Multiplication in Unary

Multiplying two unary numbers, such as '111' (for 3) and '11' (for 2), is akin to adding the first number as many times as the value of the second number. So, it involves repeated addition.

Set Initial State and Symbols

Start by marking the end of the first unary number with a distinctive symbol, say '#'. This helps in tracking when a full string has been traversed for addition.

Copy First Number

The Turing machine uses the pre-defined instruction set to copy the first unary number (e.g., '111') to a designated area on the tape, so it can be reused for multiple additions.

Use Loop for Repeated Addition

Loop through the unary representation of the second number. For each unary symbol in the second number, use the instruction set to add a copy of the first number to an accumulated result section on the tape.

Finish when Last Symbol is Processed

Once every symbol of the second number is processed and the corresponding copies of the first number are added to the result, the loop stops, leaving the result in the accumulated area on the tape.

Key concepts

Unary Numbers

Unary numbers are one of the most basic ways to represent numbers. Picture a series of identical marks, like vertical lines, that are counted to determine a number’s value. For example, the number 5 in unary form is '11111'. It’s helpful to imagine this as tally marks someone might scratch onto a board. Each '1' in a unary system represents a single unit, making it super straightforward for humans but a bit tedious for large numbers since it involves a lot of individual symbols.

Unary numbers might seem primitive, but they simplify operations like addition and multiplication when processed using Turing Machines. The simplicity of unary helps make logical, step-by-step operations visually clear on the Turing Machine’s tape.

Repeated Addition

Repeated addition is a foundational concept in multiplication. When thinking about multiplying two numbers, you can break it down into adding one of the numbers to itself multiple times. For instance, multiplying 4 and 3 essentially means adding 4 three times: 4 + 4 + 4.

In terms of unary numbers, this translates directly to counting. Suppose you are multiplying '111' (3) with '11' (2); you would add '111' repeatedly, two times. This makes it intuitive when programming a Turing Machine to handle multiplication because you’re effectively telling the machine, "add this sequence again," for every part of the multiplier.

This concept drastically reduces complex multiplication down to a series of simpler addition instructions, which is both efficient and understandable for mechanical computation.

Turing Machine Instructions

A Turing machine works through a set of predetermined instructions which guide it to read, write, and move its read/write head across a tape. These instructions form the core of how these machines perform operations, such as multiplying using unary numbers.

In the context of our original exercise, when tasked to multiply two unary numbers, the Turing Machine begins by marking the end of numbers with a special symbol, like '#', to keep track of sections on the tape. Then it uses a copy instruction to precisely replicate the needed unary sequences, allowing for repeated actions required by multiplication.

The copy function allows the first number to be duplicated each time a unit in the second number is encountered. By setting up a loop, the Turing Machine continues this process, adding each copied sequence to a growing total. These instructions essentially translate human logic into machine-readable operations, making the complex task of multiplication manageable and organized for the machine. The effectiveness of Turing Machine instructions lies in their simplicity and capability to break down intricate procedures into a linear sequence of simple steps.