When I read the latest articles on DNA computing, I had to face a rather unpleasant truth. Even though I was a geneticist who also specialized in computer science, I struggled to combine two concepts – the universal Turing machine, the very essence of computing, and the von Neumann architecture, the basis of most modern processors. I wrote C++ code to emulate the machine described in Turing’s 1936 paper and could use it to decide, say, whether a word was a palindrome. But I couldn’t understand how such a machine—with its one-dimensional tape memory and the ability to view only one character on that tape at a time—could behave like a billion-transistor processor with hardware features like an arithmetic logic unit. (ALU), program counter and instruction register.

I rummaged through old textbooks and watched online lectures on theoretical computer science, but my knowledge did not advance. I decided to build a physical Turing machine that could run code written for a real processor.

Instead of a behemoth with a billion transistors, I decided to aim for the modest 8-bit 6502 microprocessor. This legendary chip powered the computers I used in my youth. And as final proof my simulated cpu should have worked pacmanin particular, the version of the game written for the Apple II computer.

In Turing’s paper, his eponymous machine is an abstract concept with infinite memory. Actually, infinite memory is not possible, but physical Turing machines can be built with enough memory to do the task at hand. The hardware implementation of a Turing machine can be organized around a rule book and a notepad. Indeed, when we do elementary arithmetic, we use the rule book in our head (for example, we know when to carry 1). We manipulate numbers and other symbols using these rules, stepping through the process of, say, long division. However, there are key differences. We can move around the entire 2D notebook doing margin calculations before returning to the main problem. With a Turing machine, we can only move left or right on a one-dimensional pad, reading or writing one character at a time.

The key discovery for me was that the internal registers of the 6502 could be duplicated sequentially in a one-dimensional notepad using four characters – 0, 1, _ (or space) and $. The characters 0 and 1 are used to store the actual binary data that should be in register 6502. The $ character is used to represent the various registers, and the _ character acts as a marker, making it easy to return to the memory location we are working with. The main memory of the Apple II is similarly emulated.

Aside from a few flip-flops, a pair of NOT gates, and an up-and-down counter, the PureTuring machine uses only RAM and ROM chips—no logic chips. Arduino board [bottom] controls the RAM to retrieve the displayed data. James Provost

Processor programming consists of manipulating registers and transferring their contents to and from main memory using a set of instructions. I could emulate the 6502 instructions as chains of rules that acted on registers character by character. The rules are stored in programmable ROM, with the output of one rule determining which rule will be used next, what should be written in the notepad (implemented as a RAM chip), and whether we should read the next character or the previous one. .

I named my car PureTuring. The data outputs of the ROM are connected to a set of flip-flops. Some of the triggers are connected to RAM so that the next or previous character can be selected. Others are connected to their own ROM address lines in a feedback loop that selects the next rule.

It turned out that it is more efficient to interleave the bits of some registers than to leave them in separate 8-bit fragments. It took 9000 rules to create a rulebook to implement the 6502 instruction set. Of these, 2500 were created using the old-school method of writing them on index cards, while the rest were generated using a script. It took about half a year to collect all this.

Only some of the 6502’s registers are available to programmers. [green]; its internal, hidden registers [purple] used to carry out instructions. Below each register is shown how the registers are arranged and sometimes interleaved on the PureTuring “tape”.James Provost

To get a program instruction, PureTuring loops through the notepad, using the $ characters as guides, until it reaches the memory location pointed to by the program counter. 6502 opcodes are one byte long, so by the time the eighth bit is read, PureTuring is in one of 256 states. PureTuring then returns to the instruction register and writes the opcode there before proceeding to execute the instruction. It can take up to 3 million PureTuring clock cycles to fetch a single instruction compared to one to six cycles for an actual 6502!

The 6502 uses a memory-mapped I/O system. This means that devices such as displays are represented as cells somewhere in main memory. Using the Arduino to monitor the portion of the notebook that corresponds to the Apple II’s graphics memory, I could extract pixels and display them on a connected terminal or screen. This necessitated writing an “anti-vertigo” function for the Arduino, since the Apple II’s pixel data is arranged in a complex circuit. (Steve Wozniak created this circuit to allow the Apple II to emulate an analog color TV signal using digital chips and support dynamic RAM refresh.)

I could paste keyboard input into notepad the same way, but I didn’t because it’s actually a game
pacman PureTuring would have required extraordinary patience: it would take about 60 hours just to draw motion one frame for pacman character and haunting enemy ghosts. The modification, which moved the machine along a continuum to the von Neumann architecture, added a scheme to allow random access to the notepad character, eliminating the need to step through all previous characters. This adjustment has reduced the rendering time for game characters to 20 seconds per frame!

In the future, functions could be added one by one, gradually moving from a Turing machine to a von Neumann architecture: extend the bus to read eight characters instead of one, replace registers in a notebook with hardware registers, add an ALU. , and so on.

Now, when I read papers and articles about DNA computing, I can trace each element to something in a Turing machine, or jump to conventional architecture by running my own little mental machine on a concept tape!