Skip to main content
49 votes

Write a Programming language of Unknown Completeness

Legendre 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 ...
ivzem's user avatar
  • 1,309
36 votes
Accepted

Tips for Creating/Maintaining a Golfing Language

Here are some suggestions. Sorry that this partially overlaps with other answers, which have been posted as I was writing this. Design process One possibility (by all means not the only one) to ...
Luis Mendo's user avatar
  • 105k
25 votes
Accepted

Design a One Instruction Set Computer!

XOISC 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 ...
ბიმო's user avatar
  • 16.8k
23 votes

Design a One Instruction Set Computer!

Draw 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 ...
ivzem's user avatar
  • 1,309
21 votes

Build a Turing *incomplete* language

Python 2, 38 bytes lambda s,n:s.strip("()+*%n")or eval(s) Try it online! This evaluates a subset of Python 2 given by arithmetic expressions using only ...
xnor's user avatar
  • 145k
20 votes

Tips for Creating/Maintaining a Golfing Language

Here's a couple of random hints. Choose your built-in commands and values carefully Especially when your language is new, it's tempting to add lots of functionality that you think may be useful at ...
Zgarb's user avatar
  • 42.7k
17 votes

Design a One Instruction Set Computer!

-3 Here's the gist. Memory 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. ...
Conor O'Brien's user avatar
15 votes

Write a Programming language of Unknown Completeness

Union Closed This programming language is Turing complete iff the Union-closed Sets conjecture is incorrect. Controls List of Commands: x++ Increment x (INC) x-- Decrement x (DEC) j(x,y)...
fəˈnɛtɪk's user avatar
  • 4,194
15 votes

Build a Turing *incomplete* language

APL (Dyalog Unicode), 15 14 bytes (⍎⍞~'⎕⍎⍣⌶?{')⎕ Try it online! A full program that takes two inputs (an array of numbers in APL syntax, and then a line of APL ...
Bubbler's user avatar
  • 77k
14 votes

Write a Programming language of Unknown Completeness

Fermat primes 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 ...
SztupY's user avatar
  • 3,879
12 votes

Escape from the tarpit (Cops)

Blindfolded Arithmetic 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 ...
12 votes

Write a Programming language of Unknown Completeness

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 ...
fəˈnɛtɪk's user avatar
  • 4,194
11 votes

Write a Programming language of Unknown Completeness

Perfection/Imperfection 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 ...
sporkl's user avatar
  • 6,884
11 votes

Tips for Creating/Maintaining a Golfing Language

I never created a language myself, but I can partially answer number 3 (I will make this a community wiki, so feel free to add more). Some tips after the core part of your language is done: Have a ...
11 votes

Tips for Creating/Maintaining a Golfing Language

It strikes me that the most important design decision is what the underlying paradigm of the golfing language is. Here are some possible types of language: Stack based Array based Object based ...
Guillermo Phillips's user avatar
11 votes

Build a Turing *incomplete* language

APL (Dyalog Unicode), 42 bytes {∇{×|≡⊃c i←⍺:⊃c⍺⍺⍣(i⊃⍵)⊂⍵⋄c(⊣+×)@i⊢⍵}/⍺,⍵} Try it online! I thought I'd give it a go at a more "proper" submission. This function ...
Bubbler's user avatar
  • 77k
10 votes

Build a golfing language with me

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. Solutions 1. "...
Bubbler's user avatar
  • 77k
10 votes

Write a Programming language of Unknown Completeness

Soles 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 ...
fəˈnɛtɪk's user avatar
  • 4,194
9 votes

Write a Programming language of Unknown Completeness

Betrothed Betrothed Github. 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 ...
Conor O'Brien's user avatar
8 votes

Tips for Creating/Maintaining a Golfing Language

Useful integer constants Of course your golfing language has syntax that can represent any integer constant, but some integers are more useful than others. You want the useful ones to be available as ...
DLosc's user avatar
  • 39.6k
8 votes

Build a Turing *incomplete* language

JavaScript (Babel Node), 59 51 47 bytes n=>g=([a,b,c])=>c?g(a)+g(b)**g(c):b?g(a)%g(b):n Try it online! (51 bytes thanks to @user202729) This is using @...
Kyle Miller's user avatar
8 votes

Inject arbitrary code into a compiler (cops)

Vyxal 2.7 (safe) Yes, I found another another one. No, I'm not JoKing. As the rules call for deterministic languages, commands involving randomness are not allowed. Also, the ...
Aaroneous Miller's user avatar
8 votes

Inject arbitrary code into a compiler (cops)

Exceptionally (cracked by emanresu A) Exceptionally is a toy language I invented for this challenge. It is inspired by, implemented in, and transpiled to Whython (pxeger's modified version of Python 3 ...
DLosc's user avatar
  • 39.6k
6 votes

Write a Programming language of Unknown Completeness

Amicable Parity This language is based on whether there are any amicable numbers with opposite parity. Commands ...
fəˈnɛtɪk's user avatar
  • 4,194
6 votes

Unrestricted Languages

Width The interpreter is still a work in progress (I have several unused command slots still). The repo, with more documentation, can be found here. Dennis added Width to TIO less than a minute ago: ...
Stephen's user avatar
  • 13.9k
6 votes

Tips for storage in a golfing language

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 ...
NoOneIsHere's user avatar
  • 2,201
6 votes

Tips for Creating/Maintaining a Golfing Language

This relates to the implementation phase Decide Upon How the Language Will Be Executed The two most common options to implement your language are a) interpretation and b) transpilation. Interpretation ...
lyxal's user avatar
  • 33.6k
6 votes

Escape from the tarpit (Robbers)

ais523's answer - Blindfolded Arithmetic (I hope my proof is understandable. I can't check my own proof e.g. with a Try it online! link so I'm not sure) All code in this post will be Python ...
DELETE_ME's user avatar
  • 17.3k

Only top scored, non community-wiki answers of a minimum length are eligible