Re:Neurons unexpectedly encode information in the timing of ...
by tsimionescu on Wednesday July 07, 2021 @05:29PM
(#27765929)
You can simulate any quantum computer on a Turing machine, though it generally takes exponentially more time than with a real QC. Whether this means they are the same thing or not is a matter of semantics.
But what is clear is that there is no computation that can be done on a QC that can't be done on a TM.
The role of non-determinism in computation is more debatable. There is even a notable MIT professor (who coined the term Actor model) who claims that real computers, like the Android phone I'm writing this on, are in fact not Turing machines, because of non-determinism / parallelism. He also claims that Godel's incompleteness theorem doesn't apply to actual mathematics, so I would take his words with a huge spoonful of salt.
But what is clear is that there is no computation that can be done on a QC that can't be done on a TM.
The role of non-determinism in computation is more debatable. There is even a notable MIT professor (who coined the term Actor model) who claims that real computers, like the Android phone I'm writing this on, are in fact not Turing machines, because of non-determinism / parallelism. He also claims that Godel's incompleteness theorem doesn't apply to actual mathematics, so I would take his words with a huge spoonful of salt.