First, Turing machines have not been proven to solve NP-complete problems, because we have no proof of linear solutions to NP-completeness. Therefore, this Turing machine cannot solve all computational problems (at least not in tractable time).Second, Neal Stephenson has nothing to do with Turing machines. He is a cyberpunk author. Maybe you are confusing the Turing Test with a Turing machine?
First, Turing machines can quite easily solve NP-complete problems. We just don't know how to do it in *polynomial* time. (Not linear time, mind you. If our definition of tractable was linear time, then everything would be completely messed up. The reductions to show certain problems are NP-complete run in polynomial time... and pretty big polynomials. Certainly not linear.) In any case, that's part of complexity theory which isn't what the article is about.Second, this Turing machine cannot solve all computational problems, correct, but your reasoning is completely wrong. The submitter and the author of the article (and you it seems) do not know the subject matter. It can solve all _computable_ problems. (The usual term is decidable.) We don't care how much time it'll take, as long as it is finite.The guy proved the Turing machine was a Universal Turing machine, that is it is capable of running an encoding of any other Turing machine and thus any problem that any Turing machine can solve can be solved by this one by simulating it.
they are not outside turing computable.. they are computed to undefined.. which is a very important concept in computation.. these 'undefined' are not computable by anything or any machine.. they are 'undefined'..
craniumOct 26, 2007
Godel would concur, one would think.
icezzOct 26, 2007
First, Turing machines have not been proven to solve NP-complete problems, because we have no proof of linear solutions to NP-completeness. Therefore, this Turing machine cannot solve all computational problems (at least not in tractable time).Second, Neal Stephenson has nothing to do with Turing machines. He is a cyberpunk author. Maybe you are confusing the Turing Test with a Turing machine?
dnasthegreatOct 26, 2007
First, Turing machines can quite easily solve NP-complete problems. We just don't know how to do it in *polynomial* time. (Not linear time, mind you. If our definition of tractable was linear time, then everything would be completely messed up. The reductions to show certain problems are NP-complete run in polynomial time... and pretty big polynomials. Certainly not linear.) In any case, that's part of complexity theory which isn't what the article is about.Second, this Turing machine cannot solve all computational problems, correct, but your reasoning is completely wrong. The submitter and the author of the article (and you it seems) do not know the subject matter. It can solve all _computable_ problems. (The usual term is decidable.) We don't care how much time it'll take, as long as it is finite.The guy proved the Turing machine was a Universal Turing machine, that is it is capable of running an encoding of any other Turing machine and thus any problem that any Turing machine can solve can be solved by this one by simulating it.
thomashaukOct 26, 2007
Thats why your doing home economics
Closed AccountOct 26, 2007
they are not outside turing computable.. they are computed to undefined.. which is a very important concept in computation.. these 'undefined' are not computable by anything or any machine.. they are 'undefined'..
Closed AccountOct 27, 2007
quotation: "Simple Turing machine shown capable of solving any computational problem" - it is impossible
Closed AccountJan 12, 2009
can someone please explain to me what a turing machine isi even looked it up on wikipedia and i don't understand how it can simulate a computer