<p>While not exactly what you want, esoteric languages <a href="https://esolangs.org/wiki/Jot" rel="nofollow">Jot</a>, <a href="https://esolangs.org/wiki/Iota" rel="nofollow">Iota</a> and <a href="http://semarch.linguistics.fas.nyu.edu/barker/Iota/zot.html" rel="nofollow">Zot</a> could be good starting points. They are all Turing complete.</p>

<p>In particular Iota language is <a href="http://semarch.linguistics.fas.nyu.edu/barker/Iota/" rel="nofollow">defined</a> as</p>

<blockquote>
<pre><code>syntax            semantic
F --&gt; i           ^x.xSK
F --&gt; *  F  F     [F][F]
</code></pre>
</blockquote>

<p>So</p>

<blockquote>
  <p>an Iota program is either an <code>i</code>, or a <code>*</code> followed by two Iota (sub-)programs</p>
</blockquote>

<p>so it satisfies the prefix property. It's extension Zot adds input and output, where the input is the sequence of bits that follow the valid program description. By restricting Zot to programs with empty input you get a language that should satisfy your requirements. (Or alternatively adding just output to Iota.)</p>

<p>There is <a href="https://hackage.haskell.org/package/zot" rel="nofollow">Haskell implementation of Zot</a>.</p>

CC BY-SA 3.0
2015-05-18T19:06:10.180Z
2015-05-18T19:06:10.180Z
Petr
<p>A theoretical construct that comes up a lot in algorithmic computability theory is a <em>universal prefix-free language</em>. For my purposes, this is a language with the following properties:</p>

<ul>
<li><p>its syntax is defined by a binary prefix code. That is, concatenating extra digits to the end of a valid program will never result in another valid program, and if you keep choosing 0s and 1s at random indefinitely, you will eventually end up with a valid program.</p></li>
<li><p>it is Turing complete</p></li>
<li><p>its output is a stream of binary digits</p></li>
</ul>

<p>I have a slightly crazy idea that would require me to play around with an actual implementation of such a language - I want to be able to generate arbitrary (self-terminating) binary strings, have them interpreted as programs, and get binary strings as output.</p>

<p>Of course, in principle I could just invent some kind of trivial prefix-free encoding of ASCII, run it through an interpreter for my favourite language, and convert STDOUT to binary. However, if I do this, the chances of it doing anything other than terminate immediately (with a syntax error) are vanishingly small. Thus, I also have the following requirement:</p>

<ul>
<li>The language is such that a (uniformly) randomly generated program has a reasonable chance of doing something non-trivial and returning output</li>
</ul>

<p>My question is whether such a language exists - either as a formal definition in the literature that wouldn't be too time-consuming to implement, or as a command line tool or (better) a library that can be called from C++ or Python. Given the amount that has been written about this construct, I would find it mildly surprising if no-one had constructed a concrete example, but I haven't been able to track one down.</p>

CC BY-SA 3.0
2015-05-16T15:14:05.777Z
Not really relevant to your question, but isn't ASCII itself prefix-free (trivially, since all of its code words are the same length)?
svick
CC BY-SA 3.0
2015-05-16T15:36:42.960Z
@svick in this context, the prefix refers to the whole program, not just the tokens within it. So a program can never be a prefix of another program - I've attempted to make this clearer in the question.
N. Virgo
CC BY-SA 3.0
2015-05-16T16:08:28.453Z
Regarding your actual question: I must be missing something, but what you're asking sounds almost trivial to me: take a Turing machine and encode it by writing the number of states and then the state table for the transition function. Both can be encoded using a prefix-free code and the result is prefix-free language (it's self-terminating, because it's basically a length-prefixed string).
svick
CC BY-SA 3.0
2015-05-16T18:14:18.517Z
Pascal, for instance, is a naturally self-terminating Turing-complete language (if you are not too obsessed about comments appearing after the end of the program). I’m pretty sure many other real-world languages have this property. So, it seems to me that the question is based on a false premise.
Emil Jeřábek
CC BY-SA 3.0
2015-05-16T18:20:23.857Z
Oh, I see. If you want every string to be a prefix of a valid program or vice versa, take e.g. Unlambda in a suitable alphabet.
Emil Jeřábek
CC BY-SA 3.0
2015-05-16T23:56:00.097Z
@svick that's a fairly reasonable suggestion. (There are some subtleties - how do you know when you've finished reading the number and started reading the state table? - but they're easy enough to solve.)
N. Virgo
CC BY-SA 3.0
2015-05-16T23:58:52.270Z
@EmilJeřábek no, I want the opposite - *no* string that is a valid program is a prefix of a valid program, but any string that is not a valid program will eventually become one after adding enough random digits to it. I feel like I'm not explaining this very well, but it's a fairly standard concept in the work of Chaitin, Solomonoff, Hutter, that kind of stuff. Pascal would violate my fourth requirement rather severely.
N. Virgo
CC BY-SA 3.0
2015-05-17T10:53:10.400Z
No, you don't want the opposite, you want exactly what I wrote. It is impossible to guarantee that adding digits in an arbitrary way will eventually produce a valid program, unless there are only finitely many valid programs (use Konig's lemma). The best you can hope for is that every finite string that doesn't already have a valid prefix can be extended to a valid program, as I wrote.
Emil Jeřábek
CC BY-SA 3.0
2015-05-17T11:24:01.797Z
I have no idea what you're trying to achieve with the 4th requirement, but you'll be disappointed. You can't expect randomly generated program in any realistic model to do anything useful. The distribution is heavily skewed towards the shortest programs (any program of length $k$ has probability $2^{-k}$), so you can as well just generate short programs systematically and comput their statistical properties, but again, this all depends on what you want to do with the random programs, of which you said nothing.
Emil Jeřábek
CC BY-SA 3.0
2015-05-17T11:29:23.347Z
Anyway, SKI calculus in prefix notation (i.e., a variant/subset of Unlambda) is as likely as anything to have interesting short programs. I surely wouldn't expect it to be less concise than encoding of Turing machines.
Emil Jeřábek
CC BY-SA 3.0
2015-05-17T11:50:34.550Z
@EmilJeřábek (1st comment) you're right, I misunderstood you. (For some reason I thought you said every valid program is a prefix to another valid program.) (Note that I was talking about adding *random* digits, not *arbitrary* digits. If the added digits are (uniformly, independently) random then it should eventually become valid with probability 1. I believe this is equivalent to what you said.)
N. Virgo
CC BY-SA 3.0
2015-05-18T19:37:21.827Z
@EmilJeřábek: you're right about adding digits in an arbitrary way. But we can save the day and require that every *computable* way of adding more digits to a string eventually produces a valid program (because König's lemma fails by Tarski's unbouded computable tree that has no computable infinite path).
Andrej Bauer
<pl.programming-languages>
Actual practical example of a prefix-free Turing-complete language
N. Virgo
# Actual practical example of a prefix-free Turing-complete language

(Asked by: username_0 on 2015-05-16)

A theoretical construct that comes up a lot in algorithmic computability theory is a *universal prefix-free language*. For my purposes, this is a language with the following properties:

* its syntax is defined by a binary prefix code. That is, concatenating extra digits to the end of a valid program will never result in another valid program, and if you keep choosing 0s and 1s at random indefinitely, you will eventually end up with a valid program.
* it is Turing complete
* its output is a stream of binary digits

I have a slightly crazy idea that would require me to play around with an actual implementation of such a language - I want to be able to generate arbitrary (self-terminating) binary strings, have them interpreted as programs, and get binary strings as output.

Of course, in principle I could just invent some kind of trivial prefix-free encoding of ASCII, run it through an interpreter for my favourite language, and convert STDOUT to binary. However, if I do this, the chances of it doing anything other than terminate immediately (with a syntax error) are vanishingly small. Thus, I also have the following requirement:

* The language is such that a (uniformly) randomly generated program has a reasonable chance of doing something non-trivial and returning output

My question is whether such a language exists - either as a formal definition in the literature that wouldn't be too time-consuming to implement, or as a command line tool or (better) a library that can be called from C++ or Python. Given the amount that has been written about this construct, I would find it mildly surprising if no-one had constructed a concrete example, but I haven't been able to track one down.

**Tags:** pl.programming-languages

> **Comments:**
> **username_1**: Not really relevant to your question, but isn't ASCII itself prefix-free (trivially, since all of its code words are the same length)?  
> **username_0**: @username_1 in this context, the prefix refers to the whole program, not just the tokens within it. So a program can never be a prefix of another program - I've attempted to make this clearer in the question.  
> **username_1**: Regarding your actual question: I must be missing something, but what you're asking sounds almost trivial to me: take a Turing machine and encode it by writing the number of states and then the state table for the transition function. Both can be encoded using a prefix-free code and the result is prefix-free language (it's self-terminating, because it's basically a length-prefixed string).  
> **username_2**: Pascal, for instance, is a naturally self-terminating Turing-complete language (if you are not too obsessed about comments appearing after the end of the program). I’m pretty sure many other real-world languages have this property. So, it seems to me that the question is based on a false premise.  
> **username_2**: Oh, I see. If you want every string to be a prefix of a valid program or vice versa, take e.g. Unlambda in a suitable alphabet.  
> **username_0**: @username_1 that's a fairly reasonable suggestion. (There are some subtleties - how do you know when you've finished reading the number and started reading the state table? - but they're easy enough to solve.)  
> **username_0**: @EmilJeřábek no, I want the opposite - *no* string that is a valid program is a prefix of a valid program, but any string that is not a valid program will eventually become one after adding enough random digits to it. I feel like I'm not explaining this very well, but it's a fairly standard concept in the work of Chaitin, Solomonoff, Hutter, that kind of stuff. Pascal would violate my fourth requirement rather severely.  
> **username_2**: No, you don't want the opposite, you want exactly what I wrote. It is impossible to guarantee that adding digits in an arbitrary way will eventually produce a valid program, unless there are only finitely many valid programs (use Konig's lemma). The best you can hope for is that every finite string that doesn't already have a valid prefix can be extended to a valid program, as I wrote.  
> **username_2**: I have no idea what you're trying to achieve with the 4th requirement, but you'll be disappointed. You can't expect randomly generated program in any realistic model to do anything useful. The distribution is heavily skewed towards the shortest programs (any program of length $k$ has probability $2^{-k}$), so you can as well just generate short programs systematically and comput their statistical properties, but again, this all depends on what you want to do with the random programs, of which you said nothing.  
> **username_2**: Anyway, SKI calculus in prefix notation (i.e., a variant/subset of Unlambda) is as likely as anything to have interesting short programs. I surely wouldn't expect it to be less concise than encoding of Turing machines.  
> **username_0**: @EmilJeřábek (1st comment) you're right, I misunderstood you. (For some reason I thought you said every valid program is a prefix to another valid program.) (Note that I was talking about adding *random* digits, not *arbitrary* digits. If the added digits are (uniformly, independently) random then it should eventually become valid with probability 1. I believe this is equivalent to what you said.)  
> **username_3**: @EmilJeřábek: you're right about adding digits in an arbitrary way. But we can save the day and require that every *computable* way of adding more digits to a string eventually produces a valid program (because König's lemma fails by Tarski's unbouded computable tree that has no computable infinite path).  

---

## 1 answers

### Answer by username_4 on 2015-05-18. Score: 4

While not exactly what you want, esoteric languages Jot, Iota and Zot could be good starting points. They are all Turing complete.
In particular Iota language is defined as

syntax            semantic
F --> i           ^x.xSK
F --> *  F  F     [F][F]


So

an Iota program is either an i, or a * followed by two Iota (sub-)programs

so it satisfies the prefix property. It's extension Zot adds input and output, where the input is the sequence of bits that follow the valid program description. By restricting Zot to programs with empty input you get a language that should satisfy your requirements. (Or alternatively adding just output to Iota.)
There is Haskell implementation of Zot.


---

