4 ms·

> effectively turning the whole universe into one Not the whole universe, exactly. Just the parts that are possible to access :) > I’m not really sure it is a

> effectively turning the whole universe into one Not the whole universe, exactly. Just the parts that are possible to access :) > I’m not really sure it is a good rebuke of the Halting problem that “we can brute force our way out of it”. Why do you think the only way to solve the Halting problem on a model of a machine with finite memory is to brute-force our way out of it? Another person mentioned the same thing, that it would take an exponential number of steps (in the number of bits in the state space) to simulate running a program. But why are you both assuming we can only solve the problem by simulating running the program and not by analyzing the program description?

kaba0 4y ago
Now you are just back at the Halting theorem, and thus Rice’s theorem. The only question here is whether a computer is a Turing-machine, and frankly it is a weird hill to die on. With arbitrary side effects, you are back to “can the heat death of the universe be considered O(1)”, which is, well an interesting thought, but that just demonstrates infinity’s “size”.
- wizeman 4y ago
  > Now you are just back at the Halting theorem, and thus Rice’s theorem. How so? We know the Halting theorem and Rice's theorem to be decidable for finite-state machines, so how does that prove anything about the time complexity of analyzing whether the program halts? > The only question here is whether a computer is a Turing-machine For me that's an absurd question, as it's impossible to build a machine as powerful as a Turing machine. > With arbitrary side effects, you are back to “can the heat death of the universe be considered O(1)”, which is, well an interesting thought, but that just demonstrates infinity’s “size”. Sorry, I don't understand this argument :)
  - kaba0 4y ago
    As mentioned by others, a Turing machine doesn’t/can’t use infinite amount of memory, even if all it does is to step right and write a 1, it will use n bits of memory in n steps, so I don’t see how would our “finite” universe be a limiting factor here that would force our computers to be FSAs. My point regarding the heat death of the universe is that ad absurdum you can only use that amount of energy for your calculations, if every “Turing machine”-step takes a fixed amount of energy, which will indeed be a final number, and thus the O notation applies to that, making everything O(1), QED. But.. I don’t see why would the Turing machine model break down as an analogy to existing computers, programs, hell, real life (as it is one way to represent everything computable).

kaba0 4y ago

Now you are just back at the Halting theorem, and thus Rice’s theorem. The only question here is whether a computer is a Turing-machine, and frankly it is a weird hill to die on. With arbitrary side effects, you are back to “can the heat death of the universe be considered O(1)”, which is, well an interesting thought, but that just demonstrates infinity’s “size”.

wizeman 4y ago
> Now you are just back at the Halting theorem, and thus Rice’s theorem. How so? We know the Halting theorem and Rice's theorem to be decidable for finite-state machines, so how does that prove anything about the time complexity of analyzing whether the program halts? > The only question here is whether a computer is a Turing-machine For me that's an absurd question, as it's impossible to build a machine as powerful as a Turing machine. > With arbitrary side effects, you are back to “can the heat death of the universe be considered O(1)”, which is, well an interesting thought, but that just demonstrates infinity’s “size”. Sorry, I don't understand this argument :)
- kaba0 4y ago
  As mentioned by others, a Turing machine doesn’t/can’t use infinite amount of memory, even if all it does is to step right and write a 1, it will use n bits of memory in n steps, so I don’t see how would our “finite” universe be a limiting factor here that would force our computers to be FSAs. My point regarding the heat death of the universe is that ad absurdum you can only use that amount of energy for your calculations, if every “Turing machine”-step takes a fixed amount of energy, which will indeed be a final number, and thus the O notation applies to that, making everything O(1), QED. But.. I don’t see why would the Turing machine model break down as an analogy to existing computers, programs, hell, real life (as it is one way to represent everything computable).