Actual practical example of a prefix-free Turing-complete language 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.
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 --&gt; i           ^x.xSK
F --&gt; *  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.