4 ms·
Alan Turing was wrong. Correction: Alan Turing was right, but if we redefine "universal computer" in sufficiently weird ways, Turing's results no longer apply.
by cperciva 18y ago
Alan Turing was wrong.
Correction: Alan Turing was right, but if we redefine "universal computer" in sufficiently weird ways, Turing's results no longer apply.
In particular, while Turing was concerned with machines computing functions, Akl is looking at machines interacting with a changing environment.
- ewakened 18y agoYes that's a better way of putting it :) Thanks.
- frisco 18y agoHe's saying though that those two can't be separated -- the functions the machines are computing are themselves changing with time.
- cperciva 18y agothe functions the machines are computing are changing with time. 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".
- frisco 18y agoIt sounds like he's stating that a UTM can't simulate an arbitrary lambda function then, since that returns a variable function (a second-order UTM: a UTM can't simulate a UTM, which makes it not a UTM?). 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.
- davidmathers 18y agoIt sounds like he's stating that a UTM can't simulate an arbitrary lambda function then 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".
- frisco 18y agoExample: a function accepts as input the source of another program (assume it's computable and halts). Thus, the original function is variable; can it be simulated by a UTM for any arbitrary valid input? I'm probably using the wrong terminology here, but the overall logic is what I'm getting at.
- davidmathers 18y agoThe input to a function can't change (it's a fixed set). If the input changes then you've defined a new function. That's the mathematical definition of a function. You're talking about a set/class of functions, so you would need 1 UTM per function.
- dhs 18y agoTuring was simply describing what people do: in a math test, I give you a problem, you solve it - without cheating, that is, interacting with your environment - using an algorithm, you hand it back to me. He idealized what a human does - infinite time and memory -, and then, as a final step, he said: "A machine - also idealized - can do that." The important thing is that in the definition of what was later to be called "Turing computability", interaction during the computation is verboten.
- frig 18y agoBut even more to the point: the objection is that no particular 'computer' (like some physical device or at least a performance spec) could be a universal computer in his terms, b/c past a point it can't keep up. 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).
- jgrahamc 18y agoThank you for that reply. I started reading his page and it was getting stupid. He almost deliberately seems to not want to understand the definition of a Universal Computer (by which he must mean a Universal Turing Machine). 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.
- neilc 18y agoHow 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.)
- davidmathers 18y agoHow is this not complete gibberish? A function is a map from a value (set) to a value (set). The identity/definition of a function is the two values it relates. Values don't change, by definition. All he appears to be saying is that a single computer can't compute multiple functions simultaneously, which would be the non-statement of the century. Definition of function is basic set theory / category theory: http://planetmath.org/encyclopedia/Image2.html 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.
- marksutherland 18y agoHe's restricting the input functions so that they're parameterised by the variable that marks the current state of the computer. In reality this occurs often (the variable represents time) but mathematically there's no need for this. It seems to me that he's refining the model of a computer which we can realistically construct and showing that are even fewer things it can compute than its theoretical brethren.
- davidmathers 18y agoOk, I think I get it. It's really about entropy. When you create a UTM at time t=1 it's only universal at time t=1, because at time t=2 the information content of the universe has increased, and now you have the TM formerly known as universal. 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.