4 ms·

Given the author, I wonder how many states a binary TM would need to run a universe that is complex enough to contain intelligent entities that think about thin

Given the author, I wonder how many states a binary TM would need to run a universe that is complex enough to contain intelligent entities that think about things like TMs...

alluro2 3y ago
If simulation is modeling for intelligent entities thinking about the simulation, does it also model for them trying to break it and succeeding? Does that simulate the simulation breakage, or break it?
yorwba 3y ago
Apparently, a universal turing machine (that can simulate any other TM) with binary alphabet and only 15 states is known: https://en.wikipedia.org/wiki/Universal_Turing_machine#Smallest_machines https://en.wikipedia.org/wiki/Universal_Turing_machine#Small...
- jerf 3y ago
  Counterintuitively, the less you specify the universe, the less you need to run it. What happens is your runtime bloats like crazy, exponentially or even beyond. But the TM itself becomes simpler and simpler as you remove constraints. The TM to run all possible TMs is not complicated. Putting it together is an extended homework problem. Probably even easier to put together the lambda calculus expression to evaluate all possible lambda calculus expressions, or the equivalent in other TM-complete computation models. (We use TMs because they have some nice proof characteristics but we pay for those with the difficulty of "programming" them.) To say our universe is "certainly" in there is a difficult statement to prove, but all possible arbitrarily-precise simulations of it must be, even if an "arbitrarily precise" simulation functions with an arbitrarily-large lookup table of the random results of quantum interactions. The TM that runs all TMs isn't just running all the cute little TMs with 12 states that reverse a string or something. It runs all of them. Even the ones with Tree(Tree(3)) states in them. Even the ones with numbers of states that make Tree(Tree(3)) look tiny. And then the ones that make those look tiny, and so on. It's just that the resources required to run this are effectively infinite, on the grounds that no universe could ever have enough resources to reach its own execution, let alone anything else.
  - tromp 3y ago
    > Probably even easier to put together the lambda calculus expression to evaluate all possible lambda calculus expressions To wit, T = (λ 1 1) (λ (λ λ λ 1 (2 (λ λ λ 3 1 (2 (λ 2)))) (3 (λ 4 (λ 4 (2 1))))) (1 1)) (λ 1) is (denoted with de Bruijn indices) a binary tree containing all closed lambda terms. For example identity may be found at T 1 1 0 1 0 1 1 0 1 0 0 0 1 1 0 1 0 0 0, where 0 = \x\y.x and 1 = \x\y.y move to the left and right subtree respectively.
- arethuza 3y ago
  Good answer, but I was thinking more of a BB style TM that starts with an empty 'pre-Big Bang' tape.

Given the author, I wonder how many states a binary TM would need to run a universe that is complex enough to contain intelligent entities that think about things like TMs...

alluro2 3y ago

If simulation is modeling for intelligent entities thinking about the simulation, does it also model for them trying to break it and succeeding? Does that simulate the simulation breakage, or break it?

yorwba 3y ago

Apparently, a universal turing machine (that can simulate any other TM) with binary alphabet and only 15 states is known: https://en.wikipedia.org/wiki/Universal_Turing_machine#Smallest_machines https://en.wikipedia.org/wiki/Universal_Turing_machine#Small...

jerf 3y ago
Counterintuitively, the less you specify the universe, the less you need to run it. What happens is your runtime bloats like crazy, exponentially or even beyond. But the TM itself becomes simpler and simpler as you remove constraints. The TM to run all possible TMs is not complicated. Putting it together is an extended homework problem. Probably even easier to put together the lambda calculus expression to evaluate all possible lambda calculus expressions, or the equivalent in other TM-complete computation models. (We use TMs because they have some nice proof characteristics but we pay for those with the difficulty of "programming" them.) To say our universe is "certainly" in there is a difficult statement to prove, but all possible arbitrarily-precise simulations of it must be, even if an "arbitrarily precise" simulation functions with an arbitrarily-large lookup table of the random results of quantum interactions. The TM that runs all TMs isn't just running all the cute little TMs with 12 states that reverse a string or something. It runs all of them. Even the ones with Tree(Tree(3)) states in them. Even the ones with numbers of states that make Tree(Tree(3)) look tiny. And then the ones that make those look tiny, and so on. It's just that the resources required to run this are effectively infinite, on the grounds that no universe could ever have enough resources to reach its own execution, let alone anything else.
- tromp 3y ago
  > Probably even easier to put together the lambda calculus expression to evaluate all possible lambda calculus expressions To wit, T = (λ 1 1) (λ (λ λ λ 1 (2 (λ λ λ 3 1 (2 (λ 2)))) (3 (λ 4 (λ 4 (2 1))))) (1 1)) (λ 1) is (denoted with de Bruijn indices) a binary tree containing all closed lambda terms. For example identity may be found at T 1 1 0 1 0 1 1 0 1 0 0 0 1 1 0 1 0 0 0, where 0 = \x\y.x and 1 = \x\y.y move to the left and right subtree respectively.
arethuza 3y ago
Good answer, but I was thinking more of a BB style TM that starts with an empty 'pre-Big Bang' tape.