3 ms·
Something like this? https://en.m.wikipedia.org/wiki/Halting_problem https://en.m.wikipedia.org/wiki/Halting_problem
by dboreham 5y ago
Something like this? https://en.m.wikipedia.org/wiki/Halting_problem https://en.m.wikipedia.org/wiki/Halting_problem
- dane-pgp 5y agoWe can prove that it is a logical impossibility for some algorithm to exist, but I don't think we can say, given an algorithm with a certain set of steps, that there isn't an equivalent algorithm that requires fewer steps. Also, "steps" here would have to be measured in terms of operations on a physical machine (or at least an idealised perfectly efficient physical machine), but different architectures would allow different operations, and that's before we start considering different models of computation.