Turing Paint

Input:


Description

Turing Paint is an esoteric visual programming language. It uses images to represent programs. Programs can be directly run on this webpage using the "Choose File" button above. Turing Paint is a Turing-complete language. Six colors can be used: black, white, red, green, yellow, and blue. It is designed to be easy to learn and images can be created using any graphics editor. Programs can be hand-drawn without the need for any pixel fine-tuning.

Turing Paint was created by Byron Knoll in 2020. You can email me at byron@byronknoll.com for any questions or comments. In particular, let me know if you can find a program which follows all of the instructions below but doesn't execute correctly. The JavaScript code used for running Turing Paint programs is open source and released into the public domain.

Instructions

  1. Colors do not need to be exact. Anything close to one of the six colors (black, white, red, green, yellow, and blue) will be interpreted as that color. Here is an example graphics editor that can be used. When working with a graphics editor, prefer to use a tool that does not use anti-aliasing at color borders. The reason is that the anti-aliased pixels can potentially be interpreted as the wrong color, introducing noise which might make the program invalid. Resizing images (with interpolation) can also cause invalid programs for the same reason.

  2. Turing Paint programs are run on a simulated Turing machine. There is a tape of binary symbols, initialized to '0' by default. In the "Input" text field, you can enter '0's and '1's to initialize the tape to different values. The "head" will initially start at the first position of the given input. A program can cause the head to move left/right and read/write symbols. After a program has finished running, the output will display the binary states of the tape, for every position that has been written to.

  3. The image background should be white. The image should contain a single green region, which represents the "start" of the program. The green region should be completely surrounded by the white background, except for a single connection to a black region. Here is an example:start

  4. All regions and connections between regions should be at least two pixels wide. When connecting regions, they should have a single uninterrupted border (without any gaps or other colors between them).

  5. Black regions control the flow of program execution. They are used to connect other colored regions to each other. Program execution contains three steps, always in the same order: 1) branch 2) write 3) move. These are explained further below. These three steps can be repeated to create longer programs. The start (green) region should be connected to a single branch using a black region.

  6. branchThis is a branch. When program flow reaches a branch, the tape at the current head position is read. If the tape is '0', the blue branch will be followed. If the tape is '1', the red branch will be followed. At the beginning of the branch, three colors should be connected to each other: black, red, and blue. There should be a single "output" black region connected to the red region, and another connected to the blue region.

  7. After a branch, there should be a write operation (red = write '1', blue = write '0'), followed by a move operation (red = move one position left, blue = move one position right). Black regions should be used to connect the branch output to a single write operation, and the write operation to a single move operation. After a write operation, a black region can be used to connect to another branch (which can either be new or previously existing). Black regions should never be connected to multiple branches. Here is an example program with annotations:
    tutorial

  8. bridge This is a bridge. It allows two black regions to "skip" over each other without connecting. A bridge is a yellow region connected to four black regions. See the annotated example above to see how the direction of program execution flows through the bridges.

  9. Program execution will stop when there is a dead end after a move operation (i.e. there is no branch connected).

  10. Programs that follow all of the instructions above will always be valid. However, it is also possible to create valid programs while violating some of the instructions. For example, images can actually have multiple green regions, and only the first one encountered (during a raster scan) will be used. Any image which successfully runs using the Turing Paint JavaScript implementation on this webpage is technically a valid program. The implementation uses the "marching squares" algorithm to trace a path through the image, following color borders.