In class last week, my professor commented and said that Turing machines are used as a standard measure/model of what is computable and are a helpful basis of discussion for that subject. She also said that all variants of Turing machines are proven to be computationally equivalent -- read, just as powerful -- as one another. W
I commented and said yesterday that, regarding computability power, I noticed that some turing machines can take incredibly large amounts of time to compute something very simple, while a turing machine with more tapes can compute something in a lower asymptotic complexity with respect to the number of steps needed.
She said that with respect to class discourse, the runtime of a particular algorithm on a turing machine does not change the definition of computability, or the power with which we measure computability. "We're concerned about what is computable, not what is efficiently computable at this point." So, it doesn't matter if the turing machines has more and more tapes, and more and more tapes implies that it can compute in lesser steps. Okay, I get that we're really focusing on what IS computable, not the speed at which we can compute it.
Something about that just bothers me, because up to this point, algorithms with abnormally large asymptotic time and space complexity really define the limits of what is, maybe I should say, practically, computable.
So, I have a couple of questions:
- Suppose we have a model for a quantum turing machine, this must be equivalent to a "regular" turing machine, right?
So, the answer to that question I think really is going towards my reason for writing this post. Does quantum computing technology antiquate the classical definitions of what is computable via a turing machine?
- Is this something above my head and should I delete this post? I don't mean to be precocious, I just didn't see a question similar to mine.