Wakka Wakka! This Turing Machine Plays Pac-Man

When reading the most recent studies on DNA-powered computing, I faced a very unpleasant reality. While I was a geneticist and also studied computing science, I found myself attempting to make sense of two concepts – the all-encompassing Turing machine that is the core of computing as a whole and the von Neumann architecture that is the foundation of all modern CPUs. I wrote C++ code to simulate the Turing machine as described in his 1936 work and could use it to determine, for instance, whether words were palindromes. However, I was unable to see how a machine with its tape memory that is one-dimensional and the capability to view only one symbol on the tape at a given time–would behave as a billion transistor processor equipped with hardware functions such as an Arithmetic Logic Unit (ALU) as well as a program counter or instruction register.

I looked through old textbooks and watched online videos on theoretical computer science; however, my knowledge continued. I built a Turing machine to run software written for a genuine processor.

Instead of a billion transistor behemoth, I focused on the simple eight-bit 6502 microprocessor. The fabled microprocessor powered many of the computer systems I used as a kid. For a final confirmation that my computer simulation must run Pac-Man, especially the version designed for an Apple II computer.

In Turing’s work, his famous machine is an abstract idea with an infinite memory. Infinite memory isn’t feasible in real life, but physical Turing machines can be constructed with enough memory to handle the job. A rule book and a notepad could structure the hardware-based implementation of the Turing machine. When doing basic math, we utilize rules in our heads (such as being aware of when to carry the number 1). We manipulate the numbers and symbols with these rules and then go through the procedure to do, for instance, long division. There are some key distinctions, however. It is possible to move across the two-dimensional pad, making scratch calculations within the margin before returning to the main issue. With the Turing machine, we only move left and right on a single-dimensional notepad by simultaneously reading or writing a single symbol.

One of my most important discoveries was that internal registers in the 6502 could be duplicated in sequence on a one-dimensional notepad using four symbols: 0 and 1, _____ (or space), and $. The symbols 1 and 0 are used to store accurate binary data that would be stored in the 6502’s register. The $ symbol is utilized to distinguish different records, and the _ character serves as a marker, making it simple to return to a specific spot within the memory we’re working on. The primary memory of Apple II is emulated similarly.

In addition to flip-flops, a few NOT gates, and an up-down counter, The PureTuring machine is based on RAM and ROM chips. There are none of the logic chips. The Arduino board monitors the RAM to collect the display information. JAMES PROVOSTProgramming a CPU consists of manipulating registers and transferring their contents to memory and out of it using the instruction set. I could simulate the instructions of the 6502 as chains of rules that worked on the registers in a symbol-by-symbol fashion. Rules are stored inside a programable memory that outputs the result of one law dictating the following direction to be applied, what information should be recorded onto the notepad (implemented as a RAM chip), and whether it is better to read each symbol in turn or the preceding one.

I dubbed my machine PureTuring. The data outputs of the ROM are connected to a set of flip-flops. A few of them are linked to RAM, which allows the previous or next symbol to be pulled. Others are linked to ROM’s address lines within feedback loops that decide which rule to follow.

It proved to be more efficient to combine the register’s bits instead of separating them into distinct chunks of 8 bits. Making the rule book needed to use the 6502’s instruction set required 9000 rules. Two thousand five hundred were created by an old-fashioned way of writing these down on index cards. The remainder were made using writing a script. The process took around six months.

Only a few of the 6502 registers are accessible to programmers [green], and its internal, hidden registers [purple serve to execute instructions. Below each record is a description of how the papers are organized and sometimes interleaved within”PureTuring’s “tape.” JAMES PROVOST

To retrieve the software instruction, PureTuring steps through the notepad, using the $ symbols as landmarks until it reaches the memory location indicated by the counter in the program. The 6502 opcodes are 1 byte long, which means that at the point that eight bits have been read PureTuring has entered one of more than 256 states. After that, PureTuring goes back to its instruction register and writes the opcode there before executing the instruction. One instruction could take as much as three million PureTuring cycles instead of between one and six in the actual 6502!

The 6502 utilizes an input/output mapping system that is memory-mapped. That means devices like displays are represented as places in the main memory. Using an Arduino to monitor the notepad area, which corresponds with the Apple II’s graphic memory, I could remove pixels and display them on a terminal or a screen. This was a requirement for creating a “dozing” function for the Arduino since the Apple II’s data for pixel pixels is presented in a complicated plan. ( Steve Wozniak invented this method to allow his Apple II to fake the analog color TV signal using electronic chips and keep the dynamic RAM fresh.)

I could have added input from keyboards into the notepad in the same way; however, I chose not to since using Pac-Manon PureTuring PureTuring will require much patience: It took around 60 hours to draw a single frame of motion in Pac-Man. Pac-Man characters and the ghosts of enemies that were pursuing him. An adjustment that moved the machine towards the von Neumann architecture added circuitry that allowed unintentional access to the notepad symbol, which made it unnecessary to go through the previous marks. This change reduced the drawing time of the game characters to less than two minutes per frame!


Leave a Reply

Your email address will not be published. Required fields are marked *