Hacker News Reader

Comment by almost | Hacker News Reader

This appears to me to be a little (or in fact a lot) crackpotish.

A universal machine with capable of n operations per time unit can be simulate a universal machine capable of n+m operations per time unit. It's just a bit slower.

His argument seems to be that this will make it so slow that that it won't be able to keep up. Which is just stupid.

The Church-Turing thesis says that a universal machine can simulate any other computing machine given infinite memory. It doesn't say anything about how fast it will be :p

Maybe I'm misunderstanding this guy and he's not saying something so completely and utterly stupid. Anyone who wants to correct me please do...

View on HN

He seems to be misunderstood. Which is no surprise since he's into unconventional computation - whatever that is[1]. He's well published[2] and has chaired at least one conference on unconventional computing[3]. So that's more than I can say about my career in theoretical computer science. I suspect having unconventional thoughts alone will create some dissonance in related communities. Similar to what Doron Zeilberger gets for his beliefs in Ultrafinitism.

I agree that Akl is talking about a very specific circumstance of UTMs. How many thousands of Mathematicians and Computer Scientists have read that paper in the last 60 years and verified it? If there were ever going to be any true challenge to UTMs it had to be obscure and weird like this. That doesn't mean that I believe he's right, but I don't think he's a crackpot just unconventional.

[1] http://en.wikipedia.org/wiki/Unconventional_computing

[2] http://research.cs.queensu.ca/Parallel//publications.html#Pu...

[3] http://en.wikipedia.org/wiki/Selim_Akl#Conferences

Your right, I probably shouldn't be so quick to call someone a crackpot.

But still, unless I'm very much mistaken all he's doing is done is to expand the definition of "able to compute a function" to include "able to run fast enough to gather the input data for a function". That might be a useful definition for some things but to use that to claim that "Turing was wrong"?

His argument is deeper than that; he's basically saying that there's no such thing as a universal machine if the function being simulated meets any of the 5 criteria he lists, since the function can't be simulated (that is, you can't compute it with any less steps than running the whole thing through, and it could require up to infinite variables). I don't know if this makes it non-crackpot-ish, though; I don't have the background in formal theory tell; but it doesn't seem something like a "it'll take arbitrarily long" argument.

It doesn't seem terribly crackpotish to me. He's absolutely correct in pointing out that it's very sloppy to define "computability" as "What the Universal Turing Machine Can Do." It's also not unreasonable at all to talk about variables that change with time, and he's absolutely correct that this is a gap in complexity theory. One which should excite new grad students, because eventually it will net someone a lot of academic fame and one hell of a PhD thesis.

Personally, I'm very interested in this and I'm going to keep an eye on it.

It is quite unreasonable to talk about variables that change with time in the context of a Turing machine. If a "Universal Computer" is one that deals with variables which change during the computation due to interaction, then it is not what Turing was talking about. And if he wasn't talking about it, he can't be wrong about it.

The argument isn't about computing, it's about naming. The argument here is whether a Turing machine is really "universal".

It's naming, plus some more: Turing never named his idealized entity a "Turing machine" - that was done by others. He claimed universality for the algorithmic "Universal Computing Machine" he defined, and proved it - for algorithms. Now Akl comes along and says the "Turing machine" is not universal, but he uses interaction, not algorithm, to base his definition of computation on. So it seems to me that he's not only renaming "the Universal Computing Machine" to "the Universal Computer" by ways of "the Turing Machine", but that he is also moving the goalposts in this process.

Reply on news.ycombinator.com