I am wondering whether there is a minimal (or the shortest known) way of specifying a universal computational structure that includes a specification of a meta-circular evaluator within that structure. What are theoretical hurdles we might encounter? Is there something along these lines in the literature?

Update to elaborate a bit what I have in mind: A 1D-cellular automaton implementing the rule 110 has a very short description, but this structure is not immediately homoiconic, in fact it would require a lot of bits to make it homoiconic. Similarily, it takes quite a lot of states to implement a Turing machine in a Turing machine, but perhaps not as many. The Peano axioms are succinct, but Gödelization is complicated. On the other hand, LISP requires a decent amount of description at first, but the elegance of the language by essentially specifying an AST allows to write a LISP interpreter in a fairly short form. There seems to be some information theoretic trade-off. I am not interested in advanced language features like arithmetic, however, it just needs to be universal.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.