3
$\begingroup$

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.

$\endgroup$

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.