Wolfram's 2 state 3 color Turing machine is the simplest, although it requires an infinite non repeating input and does not have a halting state. It is also very difficult to program. https://en.wikipedia.org/wiki/Wolfram%27s_2-state_3-symbol_Turing_machine
Rule 110 cellular automata is also Turing complete and very simple. https://en.wikipedia.org/wiki/Rule_110 We could argue whether n-NOR or 2-NOR state machine is simpler, or whether these are universal since you have a fixed sized memory. It would still be an interesting challenge to find the smallest state machine that outputs the bits of enwik9 in sequence. On Sat, Nov 20, 2021 at 1:41 PM James Bowery <[email protected]> wrote: > > Algorithmic Randomness is very clear: > > A random string of bits cannot be represented as a program in fewer bits. > > On Sat, Nov 20, 2021 at 12:19 PM Jim Bromer <[email protected]> wrote: >> >> So if I see a string of counting numbers with a length greater than 3 or 4, >> I would conclude that those numbers are not "random" based on my experiences >> or samplings of strings of numbers, the psychology of elementary number >> theory and my awareness from thinking about this stuff. But that is >> psychology - sociology - and the familiarity of the sociological use of >> mathematics. It would not be based on pure mathematical analysis or >> something Platonic like that. > > Artificial General Intelligence List / AGI / see discussions + participants + > delivery options Permalink -- -- Matt Mahoney, [email protected] ------------------------------------------ Artificial General Intelligence List: AGI Permalink: https://agi.topicbox.com/groups/agi/T5ff6237e11d945fb-M79021cd9dce07bb1e6eb7896 Delivery options: https://agi.topicbox.com/groups/agi/subscription
