Suffolk

From Esolang
Jump to: navigation, search

Suffolk is a simple esoteric programming language created by User:ais523 in 2009, in an attempt to make a Turing-complete language along the same lines as Norfuck.

The language is based on a (right-infinite, but any given program can only access a finite portion) tape of unbounded nonnegative integers (each initially 0), a pointer that points to the current location on the tape, and one unbounded nonnegative integer of internal state. There are no loops or other control structures, but when the program reaches the end it is rerun from the start, in a continuous infinite loop.

Commands

There are 3 commands in Suffolk:

  • >: Move the pointer 1 space to the right.
  • <: Add the integer at the pointer to the internal state integer. Move the pointer to the first cell.
  •  !: Add 1 to the integer at the pointer, then subtract the internal state integer from it (if this would produce a result less than 0, instead set the integer at the pointer to 0). Set the internal state integer to 0, and move the pointer to the first cell.

When I/O commands are included, there are an extra 2 commands.

  • ,: Input one character from input, and add its character code (ASCII or Unicode) to the internal state integer. At EOF, instead set the internal state integer to 0.
  • .: Output the character whose character code is equal to the internal state integer minus 1; no output is performed if that internal state integer is 0.

Computational class

Suffolk was designed to be able to simulate arbitrary Minsky machines, and thus Turing complete. It is clear that Suffolk can simulate Norfuck; this can be done by setting cells on the tape that would be overwritten to 0 (say by setting a cell with value x to x+1-x, then setting the cell (which has value 1) to 1+1-1-1; to do this to the first cell, use !<!<<!, and to do it to subsequent cells, do the same thing with more >s involved); when writing to a tape element with value 0, Suffolk acts exactly like Norfuck. (Note that this construction fails if a tape element would be set to a value calculated involving its own previous value, but this can be avoided using extra tape elements as temporaries.) Because NOR logic can model any Boolean algebra operation with a finite number of variables, it's possible to create arbitrary finite state machines in this way. Additionally, by using one tape cell as a temporary, it's possible to add or subtract 1 to/from arbitrary tape elements, and to make these additions or subtractions conditional on the values of tape cells that switch between 0 and 1. Therefore, it is possible to simulate an arbitrary synchronous Boolean logical circuit with a finite number of extra unbounded integers as memory, thus making it possible to simulate arbitrary Minsky machines with it.

See also