The Abstract Computer

Feel free to add to this page as you please (for now)

The Abstract Computer is a parody of actual computers in relation to formal computer science that abstracts other common elements of computers to form a new, stupider abstract machine. It also serves as an explanation to newbies about the various facets of the abstractions in computer science.

Abstract Computers

Calling this page "The Abstract Computer" is a bit misleading, as there are multiple abstract manufacturers of abstract computers, each making at least one line.

The two most popular abstract manufacturers are Turing- the first company to release a modern abstract computer, which was based on a powerful model of sequential tapes- and Minsky- manufacturers of an alternative, cheaper type of device called a "counter machine".

Turing

Turing was the first company to release an abstract computer unto the world. Their main device, the "Post", is a machine of fairly simple design, and is explained below.

The Post

The Post has a single, infinite tape of symbols either "0" or "1" and a central reader head. The reader head contains a Flying Spaghetti Monster-brand state machine switchboard, to which the user attaches "nodes" and "wires". Each node has a 16-digit hexadecimal serial number (the first 4 digits represent the model, the rest represent the individual device number), and is connected to other nodes via one-dimensional wires.

Each wire is assigned a condition symbol, either 1 or 0, a write symbol of the same alphabet, and a direction of either "l", "r", or "h". Each edge is connected to a "source" node and a "destination" node. At any time, there is one node active, with the initial one connected to a wire at the bottom of the chassis. To use the machine, the user inserts the end of an infinite tape into the machine and turns it on by hitting a switch under the Turing logo. When the machine is turned on, it follows a simple process of the following specification:

• Look at the current symbol on the tape and tell it to the currents state.
• When the state transitions, take the write value of the edge it transitioned over and put it in the current cell. After, look at the direction and move the reader head left on the tape if it is "l", right on the tape if it is "r", or halt if it is "h".
• When halting, spit out the tape.

Of course, this isn't very powerful on its own, but that's where the FSM state machine comes in. The state machine follows this process whenever it receives a value:

• In the current state:
  • When I am told a value, look at my edges. Find the edge that has a condition symbol identical to that value.
  • Transition along that edge by changing the current state to that edge's destination.

Other Machines

Turing manufactures and sells other machines, but none of them are more powerful than the Post. Some have multiple tapes, or an extended alphabet, or even a multi-dimensional tape, but they are all identical in power to the Post, but much more expensive. Thus, they are less popular among consumers.

Post

The lead engineer for the Turing Post, feeling that his contribution was undervalued at Turing, left the company in 1941 to begin developing his own computers. Thus, the Post Corporation was formed and by 1943 had developed the first of its Canonical line of systems, the Tag. The Canonical brand also included the Tag's successors, the Cyclic Tag, and the Bitwise Cyclic Tag, as well as the Semi-Thue, a minimalist model that encouraged developers to implement their own preferred feature sets and influenced a generation of open-source development in the Canonical line.

The Tag

Post's main innovation was to affix the ends of the magnetic memory tape to form a loop. In order to accommodate arbitrary amounts of data, positioned between the device's read head and write head was a tape cutting and splicing device, capable of cutting the tape to remove portions of it or to splice in lengths of fresh blank tape. (As with most Turing devices, all of Post's computers required access to infinite lengths of tape to feed into the splicers.)

Another innovation allowed the Tag and its successors to forgo the use of a state machine. (It is said that Turing had a made an agreement with FSM to ensure they would provide no state machines to the fledgeling Post Corporation.) Instead, the device was always in the same state, and all decision-making was performed by looking up the symbols to be written in a finite table stored on a rotating punched drum (much like the drum inside a music box). The contents of the drum was the program to be executed by the machine, and so the machine could be reprogrammed by simply swapping drums.

The Tag operated by repeatedly performing the following actions in sequence:

• Read a constant-length sequence of symbols from the tape. (At least 2 symbols must be read for arbitrary computations to be possible.)
• Rotate the drum to a specific position based on the symbols read.
• Cut out or splice in a quantity of tape indicate by the data on the drum so as to accommodate the bytes to be written from the drum.
• Write out the symbols from the drum in such a way that the symbols read earlier are overwritten.

An astute reader will recognize that this device implements a queue data structure, such that all data is ready from one end of the tape and written to the opposite end. In fact, all of Tag's successors maintain this structure, while the Semi-Thue line of systems allows more free-form methods of data writing.

An optional feature that many users found invaluable was a halt-symbol detector: a device that switched off the device's main motor when the drum stopped in a specific position (called the "halt symbol position").

The Cyclic Tag

Near the turn of the 21st Century, engineers at Post developed the Cyclic Tag as Tag's more cost-effective successor, eliminating the need for the lookup step of rotating the drum to a specific position by instead having the drum rotate a fixed amount in each cycle, and dropping support for all but two symbols, 0 and 1, with the only decision made by the machine being whether or not to write out the symbols located at the drum's current position. This modification further made it possible for the system to read only a single symbol at a time. The downsides were that programming this machine was more difficult and that it lacked the optional halt-symbol detector. A third-party manufacturer eventually made a device with a secondary read head that would cut power to the computer upon reading a specific programmable sequence of symbols, but this option was expensive and its use voided Post's warranty.

The Bitwise Cyclic Tag

Not long after the development of the Cyclic Tag, a further simplification was made: the drum was replaced with a second tape containing only 0s and 1s. Writing the programs on magnetic tapes was far faster and less costly than punching them on drums, yet it turned out it was possible to easily translate the sequences stored on the drums into sequences that could be read one bit at time, and so this modification resulted in no loss of computational power. Some have even speculated it could be possible to store the program and data on the same magnetic tape, but as yet, no one has solved the engineering problem of getting one tape to pass through two different read heads at different speeds.

Abstract Accessories

Abstract computers on their own are practically useless, but various abstract accessories can be bought for them that make them more powerful. These devices build on the core nature of an abstract computer and make it more pleasant for the user.