2 ms·
Without having looked at the details, why do I feel like all of the other types of algorithms should be able to be shown to be equivalent to the sequential case
by hyperion2010 8y ago
Without having looked at the details, why do I feel like all of the other types of algorithms should be able to be shown to be equivalent to the sequential case under the assumption of local realism? That is to say, if you don't consider that an algorithm must be implemented in this universe then I suspect that many things are possible. Am I missing something here?
- sometime 8y agoConversely, those algorithms which cannot be converted to sequential possibly only run on exotic Turing Machines like ones with infinite bands or infinite parallelism and those likely don't have a physical equivalent because it looks like our universe only supports finite computation. In other words, the algorithms which violate Church-Turing might not be interesting at all, or only for analysis in an idealized setting.
- hyperion2010 8y agoIndeed. I had a similar thought, which initially seemed profound. "Maybe this means that the universe can encode the results of non sequential algorithms but no one can ever decode them. Douglas Adams was right all along!" Of course if you can't decode anything then in theory the universe is currently running an infinite number of undecodable simulations of itself right now. Related piece from Scott Aaronson [0]. 0. https://www.scottaaronson.com/blog/?p=3327 https://www.scottaaronson.com/blog/?p=3327