New answers tagged

2

For a real computer, everything is decidable. There is a (far bigger than astronomically but) finite number of possible states, so any program will eventually halt or enter the exact same state a second time, in which case it will never halt. Of course that is purely theoretical. It is (based on quantum physics and the total energy in the universe) ...


2

The difference is: since x86 machines are finite, Turing machines can decide languages (decision problems) that cannot be decided by any x86 machine. As I explained before, the idea of 'the set of decidable computations' is a category error. Decidability is a property of formal languages (or equivalently, of decision problems), not of computations. So, no,...


Top 50 recent answers are included