Shinjusou

Shinjusō

Paradigm(s)	String-rewriting
Designed by	User:sporeball
Appeared in	2026
Computational class	Turing complete (speculated)
Major implementations	Private
File extension(s)	.shin

The correct title of this article is Shinjusō. The substitution of any characters is for ease of access.

Shinjusō (真珠層; lit. "mother-of-pearl") is an esoteric programming language designed by User:sporeball in 2026. It is based on the string-rewriting paradigm, but its substitution rules and data string have a unique appearance: long rows of colorful beads.

Overview

The smallest unit of a Shinjusō program is the bead. Each bead is given one of eight colors, and can be either stock (may be removed or replaced during execution) or ironed (cannot be changed); nominally, the ANSI colors (i.e. black, red, green, yellow, blue, magenta, cyan, and white) are used, with bright colors representing stock beads and standard colors representing ironed beads.

The canonical way for a Shinjusō implementation to display a program immediately before executing it is to select a restricted set of glyphs and use them to represent all of the beads, differentiating them mainly by color. Using the single glyph o is recommended; the reference implementation uses both O and o for clarity. (The set of glyphs used to represent the program on disk may be larger.)

A full Shinjusō program consists of one or more substitution rules of the form

A -> B

and an initial data string S, where A, B, and S are rows of one or more beads without any whitespace. A and S must consist of only stock beads, while B may either consist of only stock beads, only ironed beads, or a mix of both; however, if B contains any ironed beads, they must be the same color as the corresponding beads in A.

Execution consists of following the program's substitution rules in order, returning to the first rule after executing the last, and stops once there is no rule left that can cause a change in the data string. When finished, the data string must contain one or more ironed beads, all adjacent to one another; if so, they are returned as the output, and the program is considered accepted.

Computational class

Shinjusō is known to be at least as powerful as a push-down automaton; however, because the language is a variation on the semi-Thue system, some users have speculated that it is likely to be Turing-complete.

The author used the (currently private) reference implementation to obtain the following program (12 rules), which can recognize strings consisting of some number of green beads followed by the same number of red beads (i.e. aⁿbⁿ):

O -> OO
OOO -> OO
OO -> O
OOO -> O
OO -> O
OO -> O
OO -> O
OO -> O
OO -> O
OO -> O
OO -> O
O -> o

Valid strings produce an output of one ironed cyan bead, while invalid strings reject without ironing anything:

in:  OOOO
  -> OOOOO
  -> OOOO
  -> OO
  -> O
  -> o
out: o