4 ms·

How about a 2 state 3 symbol Turing machine? That’s pretty simple, and universal too. https://en.m.wikipedia.org/wiki/Wolfram%27s_2-state_3-symbol_Turing_mach

• arethuza 6y ago
  As tromp has a meta-circular implementation of lambda calculus maybe that Turing Machine could be implemented in lambda calculus and we could have an objective measure of which one is "simplest"?
  • tromp 6y ago
    It takes 829 bits of binary lambda calculus to interpret BrainFuck, which is very simple programming language modeled after Turing Machines. A self-interpreter in BrainFuck takes well over a thousand bits though [2]. Lambda calculus is not only very simple, but also very expressive. While combinatory logic, with only S and K, is even simpler than lambda calculus, and also has a trivial binary encoding (00 for S, 01 for K, and 10 for application), the shortest known self-interpreter is 263 bits, appreciably larger than for lambda calculus. My IOCCC entry [3] has more examples of the conciseness of binary lambda calculus. [1] https://tromp.github.io/cl/Binary_lambda_calculus.html#Brainfuck https://tromp.github.io/cl/Binary_lambda_calculus.html#Brain... [2] https://arxiv.org/html/cs/0311032 https://arxiv.org/html/cs/0311032 [3] http://www.ioccc.org/2012/tromp/hint.html http://www.ioccc.org/2012/tromp/hint.html
    • alexisread 6y ago
      How does this logic compare to say Forth, APL or Joy? As far as I'm aware, they are all combinatorial languages - are they effectively implementations of SK combinators?
      • kryptiskt 6y ago
        "The Theory of Concatenative Combinators" (http://tunes.org/~iepos/joy.html http://tunes.org/~iepos/joy.html) connects combinatorial logic with Joy.
      • carapace 6y ago
        FWIW, I think concatenative notation is the simplest useful computational framework. ( https://joypy.osdn.io https://joypy.osdn.io disclosure: it's my project.) But I'm not mathematically sophisticated enough to make the formal argument.
• tromp 6y ago
  It's not directly comparable, since this Turing Machine is not a self-interpreter in the sense of interpreting arbitrary programs in a language of Turing Machines.
  • esmi 6y ago
    First off, I admit I didn’t do my homework so I have no idea what I’m talking about, but couldn’t the Turing machine make a Turing machine interpreter and therefore be a self interpreter? It is universal, no?
    • tromp 6y ago
      There's different notions of universality. In the more abstract one, you can emulate arbitrary computation by preparing the system (in case of the 2 state 3 symbol TM, its tape) in an appropriate configuration, letting it run until some the configuration satisfies some condition, and then extracting the result from the final configuration. In a more concrete one, you have a language of programs, and a universal program takes a program description as input, and interprets it. I give a slightly more formal definition of such a notion of universality, as applicable to Algorithmic Information Theory, in [1]. [1] https://tromp.github.io/cl/Binary_lambda_calculus.html#Universality https://tromp.github.io/cl/Binary_lambda_calculus.html#Unive...