Then I suppose one could then say that there is another class of "algorithmic information theory" that does not assume unbounded memory. Also, if one wants to incorporate time, Levin Search/Schmidhuber's speed prior are less rigorous than DCG NOR for the same reason that the instruction set is not specified for the UTM. DCG NOR at least has a clear unit of time: A state transition.
On Sat, Nov 20, 2021 at 1:14 PM Matt Mahoney <[email protected]> wrote: > 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-M4151a7cb2239546fcf5f2fa7 Delivery options: https://agi.topicbox.com/groups/agi/subscription
