It would surprise me if his example functions are actually computable. In his paper on the subject he comes up with a scenario in which a machine needs to compute a function of n variables that vary with time. He then places the restriction that reading each variable takes one unit of time so that once you've read the first one the value of the second one has changed and so you can't do the computation.

Then he goes on to say that if he supposes a computer capable of doing n computations at once he can get round the restriction he's imposed because he's able to read all the variables at the same time.

How is this supposed to make me think that Turing was wrong?

Having worked on software/hardware interactions quite a bit you actually see this sort of thing happen. Lots of data comes in on different ports and you need to read it all at the same time. This is solved by latching the data into a buffer which the CPU can read at its leisure.

But the fact remains that the function you are computing is actually computable (he gives the example of summing the data). He's just produced an artificial restriction on the computer being incapable of reading the data fast enough. His n-processors is a complicated way of solving what we solve with buffers.

And also who said there's a lower bound on the per-instruction speed of a Turing Machine. Sounds like this guy just needs a faster machine. After all a Turing Machine is an abstract idea, so let's just redefine it's operating speed by a factor of n and his function becomes computable.

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.)

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.

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.

In real life, we just sample data as fast as the computation will allow and accept that a large fraction of the world's information will not be part of our computation and that the computation is imperfect. For example: I'm sensing some time-varying function, perhaps an unpredictable aircraft, and it takes 10 sensor sampling cycles to compute my approximation of speed/velocity/turn rate/etc; I'm not going to compute every sample and watch my picture of the world lag behind by 10n (for n samples) -- I'm only going to run the computation on every 10th sample. It doesn't make Turing wrong, it just makes [sequential] sampling and computation of multiple unpredictable inputs slower than the rate at which the unpredictable inputs appear.

A comment up this thread states that it is silly to have a restriction that all the data must be processable in one time slice because you can just buffer it. I'm not aware of any buffering solution that does not require additional computation to read the value and store it in the buffer.

In his short list of misconceptions and responses, I think that #3 is closest to this argument. I don't know if it would be an absolute requirement that the initial collection of the data must remain an intrinsic part of the universal computer as opposed to the simpler definition that the observed data required for solving the problem must simply be supplied to the computer.

I think I'd lean toward the latter definition because it doesn't seem right to me to expect the universal computer to be responsible for both observing and recording every event in the universe as opposed to just expecting it to be able to perform a calculation on any given set of observed events.

Definition of function is basic set theory / category theory: http://planetmath.org/encyclopedia/Image2.html

EDIT: let's say the function computes the average age of all living people. So at time t=1 the domain is people alive at time 1 and at time t=2 the domain is people alive at time 2. He's saying that the input to the function is a variable called "people" which keeps changing, but that's not how it works. The input to a function is always a fixed value. The functions defined at times 1 and 2 are different functions because they're defined on different domains.

At first it struck me as absurd: "you can't build a computer for functions that don't exist." Um, right. But that's exactly it. Tomorrow there will exist functions that don't exist today.

Or, from the classification/sensor perspective: "choose any number, I can then add 1 to it and my number will be larger than yours." Um, yeah. But again the UTM is part of the universe and therefore can't contain more information than the universe. Tomorrow the quantity of information in the universe will have increased and your formerly universal TM will fail.

The speed issue is kind of a red herring. If you created the ultimate cisc computer that could compute the entire universe in a single clock cycle it would be constrained by size rather than speed. And tomorrow it would fail.

The same idea rules out the possibility of a universal computer (barring magic), too, except in the heads of theoreticians: any particular real-world computer is just a finite state machine, and a turing machine with eg 32 gb of space on the tape isn't actually universal, either (or even a turing machine).

Sure. But that's not what Turing was talking about. Give a UTM a computable function, and the UTM will compute it. Specify an infinite class of functions F(t), and of course a UTM will have trouble.

There's no contradiction here, just a really weird way of defining "function".

In order to evaluate a lambda you need to be able to compute an arbitrary function of arbitrary variables; with infinite resources, you should be able to process infinite variables? Surely there's work done on UTMs and lambdas.

The concept doesn't make sense. Lambda functions don't do anything, they're just notations. The process of beta reduction is what causes things/computation to happen. Beta reduction rewrites all the lambda functions, hence they're no longer the same functions. What you're saying is something like: a computer can't compute "computation".