3
$\begingroup$

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.

Improve this question
$\endgroup$
12
  • $\begingroup$ Not really relevant to your question, but isn't ASCII itself prefix-free (trivially, since all of its code words are the same length)? $\endgroup$
    – svick
    Commented May 16, 2015 at 15:14
  • $\begingroup$ @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. $\endgroup$
    – N. Virgo
    Commented May 16, 2015 at 15:36
  • $\begingroup$ 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). $\endgroup$
    – svick
    Commented May 16, 2015 at 16:08
  • $\begingroup$ 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. $\endgroup$
    – Emil Jeřábek
    Commented May 16, 2015 at 18:14
  • $\begingroup$ 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. $\endgroup$
    – Emil Jeřábek
    Commented May 16, 2015 at 18:20

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.