This language is only Turing-complete if and only if Legendre's conjecture is false, i.e. there exists a integer n > 0 such that there are no primes between n^2 and (n+1)^2. This language takes some inspiration from Underload, though in some respects it is very different from it.
Programs in Legendre are made up of series of positive integers (0 ...
Solves 15/16 problems so far!
The idea behind this language is to define 'snakes' that move around the text checking characters using a regex-like syntax.
A program in SnakeEx consists of a list of definitions for snakes using different sequences of commands. Snakes can spawn other ...
Shuffle (written in C++), Cracked! by Martin
Edit Martin cracked it. To see his solution, click the link. My solution has also been added.
Edit Fixed print-d command to be able to handle both registers and stacks. As this is a debugging command which is not permitted in a solution, this should not affect anyone using the previous version of the ...
ShapeScript is a naturally occurring programming language. Shape shifters (or Changelings, as they prefer to be called) can transform into a set of instructions that allows them to process data.
ShapeScript is a stack-based language with a relatively simple syntax. Unsurprisingly, most of its built-ins deal with altering the ...
Brian & Chuck, Cracked by cardboard_box
I've been intrigued for some time now by the idea of a programming language where two programs interact with each other (probably inspired by ROCB). This challenge was a nice incentive to tackle this concept at last while trying to keep the language as minimal as possible. The design goals were to make the ...
Slip, Python 3.4 (Github wiki, online interpreter)
Like feersum's submission this is also based on traversing the grid, but like CarpetPython's submission this is based on regex. Somehow it looks like I managed to take the middle ground.
There's a quite a lot of unimplemented features which I want to add, so where relevant I've noted what I intend to do ...
This OISC is based on Fokker's X-combinator which is defined as follows:
$$ X = \lambda f\ . f\ (\lambda g\ h\ x\ . g\ x\ (h\ x))\ (\lambda a\ b\ c\ . a) $$
If we acknowledge the fact that the SKI-calculus is Turing complete the above \$X\$-combinator is Turing complete as well. This is because \$S\$, \$K\$ and \$I\$ can be written in terms of \$X\$,...
Draw is an OISC acting on a 2D grid, marking squares in a manner similar to the Wang B-machine. However, to keep the language as simple and OISC-y as possible, all instructions (of which there are a grand total of one) mark the square just stepped on, and, in order to be able to halt, stepping on a marked square terminates the program.
The program ...
I envision the language as snails moving around a grid and executing commands. The snails leave a trail of slime on each square which they move onto, which by default causes the square to be subsequently unmatchable. A match is successful if the end of the list of commands is reached.
There are enough operators now that we're going to need ...
HPR, written in Python 3 (Cracked by TheNumberOne)
HPR (the name means nothing) is a language for processing lists of integers.
It is designed to be minimalistic, extremely limited, and free of "artificial" restrictions.
Programming in HPR is painful, not because you have to solve a puzzle to keep the interpreter from shouting at you, but because it's hard ...
Here's the gist.
Memory is a map of tapes, where the keys are strings and values are arbitrary-sized integers.
Additionally, there is a set of labels, where the program can jump to.
There is a stack, which contains the operands, which are strings.
There is an offset, which controls where in the memory's tapes it can access.
The One ...
Grime is based on Boolean grammars.
The basic idea is to construct rectangular patterns from smaller components, and check whether they are found in the input matrix.
So far, Grime only supports rectangular matches, and solves at least 11 problems more or less elegantly.
EDIT: Fixed the crosses (thanks to DLosc for spotting the ...
The Re2d class, Python 2
Update: added "9. Alignment" problem.
My approach is to use the Python re module to do the searching and matching. The
Re2d class prepares the text for processing, executes the re functions, and
formats the results for output.
Note that this is not a whole new language - it is the standard regular
expression language projected ...
This programming language is Turing complete iff the Union-closed Sets conjecture is incorrect.
List of Commands:
x++ Increment x (INC)
x-- Decrement x (DEC)
j(x,y) Add instruction set x if y is 0 to end of instruction queue
All variables are initialized as 0
Programs are written as a set of sets of ...
The language works on two potentially infinite tapes, where each location of the tape can store an arbitrary integer. Both tapes are filled with -1 at start. There is also two tape heads that start at position 0 on both tapes.
The interpreter will first read the input, and store the values into the first (data) tape, starting at position 0.
TKDYNS (To Kill the Dragon, You Need a Sword) - Cracked by Martin Büttner
EDIT: I've added my solution and explanation below the main post.
In this language, you take control of a valiant warrior who has been tasked with slaying a terrible dragon. The dragon lives in an underground labyrinth, full of perils and dangers, and until now, no-one ...
Template Matching and Recognition Language
My interpreter takes up 24K chars (code snippets take up characters?), so the full description can be found here.
var reservedOutsideInput = "\u0007";
var templateChar = "$"
This programming language is Turing complete iff the Scholz conjecture is true.
I wrote this language because @SztupY was saying that there wouldn't be any results that rely on the conjecture to be true to be Turing complete
List of Commands
+(x) Increment x (INC)
-(x) Decrement x (DEC)
j(x,y) Jump to instruction x if y is 0 (JZ) ...
Whew, that was fun.
Perfection/Imperfection is only complete if there are infinite perfect numbers. If there are, it's called Perfection, and if there are not, it is called Imperfection. Until this mystery is solved, it holds both names.
A perfect number is a number whose divisors sum to the number, so six is a perfect number ...
Swallows w/ Coconut v2
As the previous version had errors which made it invalid for this contest, and I don't want to have the upvotes from the previous version count for this version which is significantly different, this version is being submitted as a new post.
This language is not Turing complete if the Collatz Conjecture can be proven for all positive ...
Possibly a fairly easy language to start off with, relatively
speaking. (There are limits on how difficult a language I can make
because I have to prove it Turing-complete myself!)
For this language, the program set is the set of Blindfolded
Arithmetic programs as given in the section "program" below, the input
set is the set of ...
The readme and specification is on the github, under "README.txt".
Generally, a Betrothed program is composed of pairs of lines, whose lengths are distinct twin prime pairs or betrothed pairs (no duplicates can occur). The program is executed by find "pliable subsets" of the first line in the pair within the second line. The ...
Firetype, Cracked by Martin Büttner
A really weird mix of BF and CJam. And who knows what else! Pretty sure this'll be
an easy one, but it was fun anyway. FYI, the name is referring to Vermillion Fire from Final Fantasy Type-0.
NOTE: Please forgive me for any ambiguities in this description. I'm not the best writer... :O
Martin cracked this really quickly!...
2. Score: 2938 2583
The modified interpreter is here on TIO.
String literal is the most obvious addition to the language, mainly to combat kolmogorov-complexity challenges.
1. "Hello, World!" - 20 bytes (-28)
Any kolmogorov-complexity challenge can be completed using the structure #"<string>"[o>] ...
I suggest all of them!
More seriously, they all come in handy some of the time, and the more the better! Implicit input is never bad, just have a flag to turn it off. Variables are helpful so they don't need to be found on a stack or tape; same with registers. Stacks are helpful to store data, and so are tapes. I recommend trying to implement multiple, say ...
Picofuck is similar to Smallfuck. It operates on a binary tape which is unbound on the right, bound on the left. It has the following commands:
> move the pointer right
< move the pointer left. If the pointer falls off the tape, the program terminates.
* flip the bit at the pointer
( if the bit at the pointer is 0, jump to the next ...
... and hopefully definitely more loophole-proof.
I already read the Acc! spec. How is Acc!! different?
In Acc!!, loop variables go out of scope when the loop exits. You can only use them inside the loop. Outside, you'll get a "name is not defined" error. Other than this change, the languages are identical.
Zinc, Cracked! by @Zgarb
Also available at GitHub.
You need Dart 1.12 and Pub. Just run pub get to download the only
dependency, a parsing library.
Here's to hoping to this one lasts longer than 30 minutes! :O
Zinc is oriented around redefining operators. You can redefine all the operators
in the language easily!
The structure of a typical ...
Compass Soup (cracked by cardboard_box)
Compass Soup is kind of like a Turing machine with an infinite 2-dimensional tape. The main catch is that the instruction memory and data memory are in the same space, and the output of the program is the entire contents of that space.
How it works
A program is a 2-dimensional block of text. The ...