The Tape

The tape functions as the information repository for the Turing machine. It can simply be an extended piece of paper, ideally infinite, divided into smaller squares. On this tape, you have numerous blank sections where symbols can be inscribed.

These symbols serve to transmit information through time, making it computable.

The significance of each symbol is context-dependent, reflecting Shannon’s information theory. The symbols belong to a finite collection known as an alphabet. Our written alphabet serves as a prime example, being a limited set of shapes that correspond to the sounds we produce.

You could sketch apples if you understand what they signify, or even use the term “fantasy” as a symbol. The possibilities are endless.

Computers typically utilize binary: ones and zeros, which represent two distinctly identifiable symbols. However, alternatives like 1s and 2s or even apples and oranges could be used, provided they can be differentiated when read.

You, with a Pen

You find yourself beside the tape, pen in hand, capable of deftly drawing all conceivable symbols onto the tape. Moreover, you can recognize and differentiate all possible symbols upon viewing them.

A Notebook

The notebook contains the directives guiding your interaction with the tape. These instructions outline actions to take in various scenarios encountered while operating the machine.

Each numbered line in the notebook conveys two types of information: - What action to perform on the tape upon encountering a specific symbol. - Which line to follow next in the notebook.

You can execute two primary actions on the tape: 1. Move one square to the right, left, or remain stationary. 2. Erase the current symbol and replace it with another, or take no action.

The notebook lines provide guidance. For example, if there are eight lines, the first could state: “If you see a 0: keep the 0, move left, and proceed to line 5. If you see a 1: replace it with a 0, move right, and go to line 4.”

After completing these tasks, you transition to a different line in your notebook, continuing until you reach the final instruction. For instance, line 8 might indicate: “If you see a 0: replace it with a 1 and conclude. If you see a 1: replace it with a 0 and conclude.”

This concluding line halts all operations related to the tape.

This represents the essential structure of a Turing machine. Although actual computations may introduce complexity, the core concept remains simple.

Key Components

In summary, the primary components of a Turing machine are: 1. A finite collection of symbols referred to as an alphabet. 2. The (infinite) tape that stores these symbols and acts as the machine's memory. 3. A movable read/write head that operates on the tape, capable of shifting left, right, or remaining still based on the instructions. 4. A notebook containing the instructions, including the machine’s initial and final states, akin to the machine's processor.

Performing Computations

To execute a computation, one must develop a procedure (the lines of instructions in the notebook) that reasonably manipulates the tape symbols to achieve the desired outcome.

You can formulate procedures for addition, subtraction, multiplication, and division on a Turing machine. Furthermore, Turing's assertion that any computation can be executed with a Turing machine remains unchallenged after 80 years.

For instance, if you aim to add two numbers, the first step is determining how to represent them on the tape. The representations you choose dictate the symbols to use, and the code clarifies their meanings. This distinction is crucial: the machine itself need not comprehend the meaning of the symbols it manipulates. If using binary, a composite symbol like 1110000010101001 could signify countless meanings, depending on the code.

When discussing numbers, there exists a standard binary representation. Alternatively, one could opt for unary code: a single 1 represents one, two 1s denote two, three 1s indicate three, and so forth.

Adding Numbers

Begin by inscribing the two numbers you wish to add onto the tape in accordance with the instructions. For instance, to add 4 and 8, write them in binary format:

Input: 1 0 0 $ 1 0 0 0

Here, the dollar sign serves as a new symbol indicating the separation between numbers, resulting in three distinct symbols in your alphabet. While not obligatory, any finite alphabet can be encoded using binary, much like our decimal system. This illustrates that additional symbols can enhance conciseness.

Next, establish a procedure (lines in a notebook) to manipulate the symbols, ultimately yielding the result 12 in binary:

Output: 1 1 0 0

Procedures for basic arithmetic on Turing machines are readily available, although specifics are omitted here (additional resources exist for adding binary numbers using Turing machines).

Universal Turing Machines

Turing recognized that a notebook is unnecessary if all the information can be incorporated directly onto the tape. Universal Turing Machines function similarly to traditional Turing machines but operate without a separate notebook. The notebook essentially represents a sheet of paper containing information, which the tape also embodies. Hence, only one information-carrying medium is required.

This allows the tape to hold instructions for a specific Turing machine (similar to the eight lines of instructions earlier).

By placing these eight lines of code onto the tape, you can subsequently add the input intended for the Turing machine.

The Universal Turing Machine then executes the function as if it were the Turing machine defined by those eight lines, producing the same output as if the notebook had been used initially.

This concept mirrors modern computers, where the operational instructions, known as software, are integral to the machine itself.

Turing Machines and DNA

There are numerous parallels between the operations of Turing machines and the functioning of DNA, despite some differences: while DNA does not compute, its role diverges from that of a Turing machine, providing a fascinating perspective on the computational foundations of our genes.

Let’s explore the components: 1. The alphabet comprises the four bases (A, T, G, and C), representing the symbols inscribed on the tape. 2. The code links these symbols to the amino acids they correspond to, highlighting that the relationship is purely symbolic; there’s no inherent chemical explanation for the connection between a codon (like ACG) and the amino acid it encodes. 3. The instructions for protein synthesis are known as a gene, akin to an algorithm dictating how to construct a specific protein. 4. The tape itself is the DNA, carrying the composite symbols (codons). 5. The read/write head differs slightly from the conventional type; it functions primarily as a read-head, moving along the DNA to transcribe codons to messenger RNA, which instructs ribosomes on which amino acids to link. 6. Transcription factors, which are proteins binding to DNA sequences, regulate the transcription of certain genes, influencing the machine's state by determining which parts of the tape are transcribed. 7. There are start/stop codons (specific base sequences) that signify the beginning and end of the transcription process. 8. The output can be viewed as the proteins produced, though this output is qualitatively different from that generated by a standard Turing machine (which would involve something written on the tape).

It is truly remarkable that nature has devised this machinery through evolutionary processes, particularly from the formal standpoint of Turing machines.

Equally astonishing is the progress humanity has made over the last 80 years in constructing computers. Turing's research laid the foundation for understanding the potential of computing devices (although Charles Babbage and Ada Lovelace made significant contributions with the difference engine a century earlier) and for realizing that all computations could be distilled into executing simple tasks.

It would have seemed absurd back then to envision the creation of the device you are likely using to read this article (a time when Watson allegedly suggested that “there is a world market for maybe five computers”).

The modern computer stands as a testament to human ingenuity: our capacity to conceive ideas, demonstrate their feasibility, and possess the courage and persistence to bring them to fruition.