Sloopy

Sloopy is a language intended to be used in proofs of Turing-completeness, in particular for showing that Burro is Turing-complete. It started life as a C-like language, but the author soon realized their mistake (if you can call 6 months "soon"), and pivoted it to be a brainfuck-like language.

Given how many brainfuck-like languages there are, the chances that it has the same semantics as some other brainfuck-like language already on this wiki, are quite high, and it is thus quite likely that "Sloopy" is simply another name for that language.

Overview

Like brainfuck, Sloopy programs consist of the following symbols:

• [ begin "while" loop
• ] end "while" loop
• + increment current cell
• - decrement current cell
• < move one cell left on tape
• > move one cell right on tape

There are a few additional symbols which will be explained in a moment:

• ( begin "if-else" block
• / seperate "if" from "else" part inside "if-else" block
• ) end "if-else" block

Unlike brainfuck, there are some syntactic rules on the use of the symbols. If a program doesn't conform to these rules, it shall be rejected outright.

• The first symbol in the program must be [, the final symbol must be ], and there must be no other occurrences of these two symbols in the program.
• Every ( must have a matching ), and in between these symbols there must be exactly one / symbol. The / symbol must not appear outside of a pair of ( and ) symbols.

Like brainfuck, there is a single tape head that can move around in the tape, and the only thing that moves the head is execution of < and > instructions. Like brainfuck, each cell of the tape contains an integer value, and the only thing that alters the value in the current cell (the one under the head) is the execution of + and - instructions.

Unlike brainfuck, all cells of the tape are initially zero except for the first cell, which is initially 1. Unlike most(?) brainfucks, the tape is infinite in both directions, and the integers stored on the tape are unbounded in both the positive and negative extents.

The semantics of (.../...) are pedestrian: it is an if-else block. When executing (, if the current cell is non-zero, the instructions between the ( and / are executed; conversely, if it is zero, the instructions between the / and ) are executed; and in either case execution then resumes after the closing ).

Computational class

The author claims that Sloopy is Turing-complete. It is the case that every Turing machine can be simulated by some Turing machine with a single loop (see, for example, page 281 of Computation: Finite and Infinite Machines). Any Turing machine with a single loop can be translated to a Sloopy program using the same general techniques that allow us to say that any Turing machine (with any number of loops) can be translated to a brainfuck program (with any number of loops).

Alternatively, Sloopy can trivially be shown to be Turing-complete using The Waterfall Model, which it can implement almost directly. You use one tape cell to determine whether the waterclocks have been initialised – with 0 meaning uninitialised and 1 meaning initialised – and only finitely many other tape cells are ever accessed, each directly representing a waterclock (the cell that is initially 1 is the halt waterclock). Both the steady decrement and zeroing trigger of The Waterfall Model translate directly into Sloopy, so you simply start the loop by checking to see whether the waterclocks have been initialised (initialising them if they haven't been, and setting the "initialised" flag to 1), then follow it by the zeroing triggers and steady decrement. If the halt waterclock ever becomes 0 (halting the emulated program), that will cause the outer loop to stop, halting the Sloopy program too.

Variation

There is a variation where, while there still must be only one [ and only one ], and they must still appear in that order, they need not be the initial and final symbols in the program. To translate from this variation to standard Sloopy, introduce conditional blocks just after the [ (checking if this is the first time through the loop) and just before ] (checking if this is the last time we will be in the loop), and execute the prelude and postlude code sequences in those conditionals.

In this variation there is no need for the initial tape cell to be 1 instead of 0, and it would probably be more natural to have all tape cells start as 0 in this case. (Most programs would ensure they modify some cell to be non-zero and move the head to it just before the first execution of the [.)