patternCritical
Is a Turing Machine "by definition" the most powerful machine?
Viewed 0 times
definitionthepowerfulmachineturingmost
Problem
I agree that a Turing Machine can do "all possible mathematical problems". But that is because it is just a machine representation of an algorithm: first do this, then do that, finally output that.
I mean anything that is solvable can be represented by an algorithm (because that is precisely the definition of 'solvable'). It is just a tautology. I said nothing new here.
And by creating a machine representation of an algorithm, that it will also solve all possible problems is also nothing new. This is also mere tautology. So basically when it is said that a Turing Machine is the most powerful machine, what it effectively means is that the most powerful machine is the most powerful machine!
Definition of "most powerful": That which can accept any language.
Definition of "Algorithm": Process for doing anything.
Machine representation of "Algorithm": A machine that can do anything.
Therefore it is only logical that the machine representation of an algorithm will be the most powerful machine. What's the new thing Alan Turing gave us?
I mean anything that is solvable can be represented by an algorithm (because that is precisely the definition of 'solvable'). It is just a tautology. I said nothing new here.
And by creating a machine representation of an algorithm, that it will also solve all possible problems is also nothing new. This is also mere tautology. So basically when it is said that a Turing Machine is the most powerful machine, what it effectively means is that the most powerful machine is the most powerful machine!
Definition of "most powerful": That which can accept any language.
Definition of "Algorithm": Process for doing anything.
Machine representation of "Algorithm": A machine that can do anything.
Therefore it is only logical that the machine representation of an algorithm will be the most powerful machine. What's the new thing Alan Turing gave us?
Solution
I agree that a Turing Machine can do "all the possible mathematical problems".
Well, you shouldn't, because it's not true. For example, Turing machines cannot determine if polynomials with integer coefficients have integer solutions (Hilbert's tenth problem).
Is Turing Machine “by definition” the most powerful machine?
No. We can dream up an infinite hierarchy of more powerful machines. However, the Turing machine is the most powerful machine that we know, at least in principle, how to build. That's not a definition, though: it is just that we do not have any clue how to build anything more powerful, or if it is even possible.
What's the new thing Alan Turing gave us?
A formal definition of algorithm. Without such a definition (e.g., the Turing machine), we have only informal definitions of algorithm, along the lines of "A finitely specified procedure for solving something." OK, great. But what individual steps are these procedures allowed to take?
Are basic arithmetic operations steps? Is finding the gradient of a curve a step? Is finding roots of polynomials a step? Is finding integer roots of polynomials a step? Each of those seems about as natural. However, if you allow all of them, your "finitely specified procedures" are more powerful than Turing machines, which means that they can solve things that can't be solved by algorithms. If you allow all but the last one, you're still within the realms of Turing computation.
If we didn't have a formal definition of algorithm, we wouldn't even be able to ask these questions. We wouldn't be able to discuss what algorithms can do, because we wouldn't know what an algorithm is.
Well, you shouldn't, because it's not true. For example, Turing machines cannot determine if polynomials with integer coefficients have integer solutions (Hilbert's tenth problem).
Is Turing Machine “by definition” the most powerful machine?
No. We can dream up an infinite hierarchy of more powerful machines. However, the Turing machine is the most powerful machine that we know, at least in principle, how to build. That's not a definition, though: it is just that we do not have any clue how to build anything more powerful, or if it is even possible.
What's the new thing Alan Turing gave us?
A formal definition of algorithm. Without such a definition (e.g., the Turing machine), we have only informal definitions of algorithm, along the lines of "A finitely specified procedure for solving something." OK, great. But what individual steps are these procedures allowed to take?
Are basic arithmetic operations steps? Is finding the gradient of a curve a step? Is finding roots of polynomials a step? Is finding integer roots of polynomials a step? Each of those seems about as natural. However, if you allow all of them, your "finitely specified procedures" are more powerful than Turing machines, which means that they can solve things that can't be solved by algorithms. If you allow all but the last one, you're still within the realms of Turing computation.
If we didn't have a formal definition of algorithm, we wouldn't even be able to ask these questions. We wouldn't be able to discuss what algorithms can do, because we wouldn't know what an algorithm is.
Context
StackExchange Computer Science Q#66746, answer score: 143
Revisions (0)
No revisions yet.