3 ms·

How is this supposed to make me think that Turing was wrong? Akl would certainly not claim that "Turing was wrong" -- the submitted title is obvious flamebait.

by neilc 18y ago

How is this supposed to make me think that Turing was wrong? Akl would certainly not claim that "Turing was wrong" -- the submitted title is obvious flamebait. He's just produced an artificial restriction on the computer being incapable of reading the data fast enough. Well, he is assuming a different model of computation. Whether it is "artificial" or not is debatable: in an actual physical system, you can't pause the world, fix all the inputs, and then compute for an arbitrary length of time. In any case, this is theoretical work: investigating the nature of computation under a different set of assumptions is perfectly valid, and I think it's very interesting. let's just redefine it's operating speed by a factor of n and his function becomes computable. For a given function, sure. But unless your machine can perform an infinite number of computations per time step, no machine will be fast enough to compute all possible functions, which is the point. (BTW, I took some classes with Akl as an undergrad. He's a very sharp guy, and a great professor -- and definitely not a crackpot.)

antipax 18y ago
>>> For a given function, sure. But unless your machine can perform an infinite number of computations per time step, no machine will be fast enough to compute all possible functions, which is the point. I mentioned this somewhere further down in the comments, but a machine that could perform an infinite number of computations would break Turing's proof of the undecidability of the halting problem over Turing machines. That probably furthers Akl's claim. I most definitely think this is interesting in that it is a new set of assumptions about what a computer is and what it should be capable of doing. All we have to do now is define a new (probably recursively-defined) automaton capable of infinite growth in it's possible inputs. Then again, if a computer had an infinite amount of inputs, that raises even more interesting questions about what problems possibly then become decidable.
jerf 18y ago
neilc: "Akl would certainly not claim that "Turing was wrong" -- the submitted title is obvious flamebait." Akl: "The consequences to theoretical and practical computing are significant. Thus the conjectured "Church-Turing Thesis" is false. It is no longer true that, given enough time and space, any single general-purpose computer, defined a priori, can perform all computations that are possible on all other computers. Not the Turing Machine, not your laptop, not the most powerful of supercomputers. In view of the computational problems mentioned above (and detailed in the papers below), the only possible universal computer would be one capable of an infinite number of operations per time unit." Me: It sure sounds like he's claiming Turing, in the Church-Turing Thesis, is false.

by neilc 18y ago

antipax 18y ago

>>> For a given function, sure. But unless your machine can perform an infinite number of computations per time step, no machine will be fast enough to compute all possible functions, which is the point. I mentioned this somewhere further down in the comments, but a machine that could perform an infinite number of computations would break Turing's proof of the undecidability of the halting problem over Turing machines. That probably furthers Akl's claim. I most definitely think this is interesting in that it is a new set of assumptions about what a computer is and what it should be capable of doing. All we have to do now is define a new (probably recursively-defined) automaton capable of infinite growth in it's possible inputs. Then again, if a computer had an infinite amount of inputs, that raises even more interesting questions about what problems possibly then become decidable.

jerf 18y ago

neilc: "Akl would certainly not claim that "Turing was wrong" -- the submitted title is obvious flamebait." Akl: "The consequences to theoretical and practical computing are significant. Thus the conjectured "Church-Turing Thesis" is false. It is no longer true that, given enough time and space, any single general-purpose computer, defined a priori, can perform all computations that are possible on all other computers. Not the Turing Machine, not your laptop, not the most powerful of supercomputers. In view of the computational problems mentioned above (and detailed in the papers below), the only possible universal computer would be one capable of an infinite number of operations per time unit." Me: It sure sounds like he's claiming Turing, in the Church-Turing Thesis, is false.