Brian & Chuck

Brian & Chuck is an esoteric programming language with two mutually modifying Brainfuck-like programs developed by user:Martin Ender. The language was remotely inspired by RubE on Conveyor Belts and Self-modifying Brainfuck.

The design goals were to make the language Turing-complete while each of its parts individually are not Turing-complete. Furthermore, even both of them together should not be Turing-complete without generating code at runtime. I (the author) think I've succeeded with that, but I haven't proven any of those things formally yet.

Added by User:LuisCR: I have proved that this language is Turing-complete. See below.

Overview

Brian and Chuck are two brainfuck-like programs. Only one of them is being executed at any given time, starting with Brian. The catch is that Brian's memory tape is also Chuck's source code. And Chuck's memory tape is also Brian's source code. Furthermore, Brian's tape head is also Chuck's instruction pointer and vice versa. The tapes are semi-infinite (i.e. infinite to the right) and can hold signed arbitrary-precision integers, initialised to zero (unless specified otherwise by the source code).

Since the source code is also a memory tape, commands are technically defined by integer values, but they correspond to reasonable characters. The following commands exist:

• , (44): Read a character from STDIN into the current memory cell. Only Brian can do this. This command is a no-op for Chuck.
• . (46): Write the current memory cell, modulo 256, as a character to STDOUT. Only Chuck can do this. This command is a no-op for Brian.
• + (43): Increment the current memory cell.
• - (45): Decrement the current memory cell.
• ? (63): If the current memory cell is zero, this is a no-op. Otherwise, hand control over to the other program. The tape head on the program which uses ? will remain on the ?. The other program's tape head will move one cell to the right before executing the first command (so the cell which is used as the test is not executed itself).
• < (60): Move the tape head one cell to the left. This is a no-op if the tape head is already at the left end of the tape.
• > (62): Move the tape head one cell to the right.
• { (123): Repeatedly move the tape head to the left until either the current cell is zero or the left end of the tape is reached.
• } (125): Repeatedly move the tape head to the right until the current cell is zero.

The overall program terminates when the active program's instruction pointer reaches a point where there are no more instructions to its right.

Source Code

The source file is processed as follows:

• If the file contains the string ```, the file will be split into two parts around the first occurrence of that string. All leading and trailing whitespace is stripped and the first part is used as the source code for Brian and the second part for Chuck.
• If the file does not contain this string, the first line of the file will be used as the source for Brian and the second part for Chuck (apart from the delimiting newline, no whitespace will be removed).
• All occurrences of _ in both programs are replaced with NULL bytes. This allows you to insert zero cells more easily into the source.
• The two memory tapes are initialised with the character codes corresponding to the resulting string.

As an example, the following source file

  abc
```
0_1
23

Would yield the following initial tapes:

Brian: [97 98 99 0 0 0 0 ...]
Chuck: [48 0 49 10 50 51 0 0 0 0 ...]

Examples

This prints Hello, World!:

?Hello, World!
!>.>.>.>.>.>.>.>.>.>.>.>.>.

This is a cat program:

?_{<{<{}<,+?>>}>}>}<?_{<-?+>>}<?__{<?
!}>}>}+{<{<{?_{<{<}>}>}<+{<?_}<--.>_{<-?+{<{<?

Turing-Completeness Proof

This section shows how to reduce a Turing machine to Brian & Chuck.

Suppose that the machine has m states (numbered 0,1,...,m-1) and n symbols (numbered 0,1,...,n-1). Brian's tape consists in mn sections (each one starting with a 0) and never changes. Chuck's tape has a section for each simulated tape cell. A section for the symbol i contains: _!{<{<...<{ with mn braces, followed by >|>|...>| with m-1 >|s, then i repetitions of >}>}...>} with m >}s, n-1-i repetitions of >|>|...>| with m >|s, and ends with {<?.

At the beginning of a cycle in state s, Brian's pointer is at some position (it doesn't matter where), Chuck's pointer is at the exclamation mark at the start of a section, and the first s vertical bars are changed to closing braces. Chuck starts running the section. First, Brian's pointer is sent to the start, then it is advanced exactly s+mi sections, and the {<? triggers the section s+mi (where the first section is 0).

Now Brian's section does the following things:

1. Edit the symbol in Chuck's section.
2. Erase the state information (with < and -).
3. Move to a new section: left with {< and right with }>.
4. Write the new state (with > and +)
5. Attempt to fire the section with {>?. If it succeeds, we are done. Otherwise, the section is not initialized.
6. Initialize the section with a lot of >s and +s (the state is already written with 1's at the correct positions, so just write |s that will become }s).
7. Then do {>? again; it should succeed.

External Resources

• GitHub repository including language spec, reference implementation in Ruby (with some additional debug features, see README.md) and example programs.
• Online interpreter at Try It Online.