Re:Church-Turing Thesis Cannot Possibly Be True [video]
by sometime on Friday October 19, 2018 @03:03AM
(#18254698)
Conversely, 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.
[ Parent
| on HN ]
Re:Church-Turing Thesis Cannot Possibly Be True [video]
by hyperion2010 on Friday October 19, 2018 @03:29AM
(#18254791)
Indeed. 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].