5 ms·

Non-Universality in Computation: The Myth of the Universal Computer

46 points by ewakened 18y ago

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 ago
  Yes that's a better way of putting it :) Thanks.
- frisco 18y ago
  He's saying though that those two can't be separated -- the functions the machines are computing are themselves changing with time.
  - cperciva 18y ago
    the 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 ago
      It 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 ago
        It 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 ago
        Example: 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 ago
        The 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 ago
    Turing 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 ago
  But 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 ago
  Thank 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 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.)
- davidmathers 18y ago
  How 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 ago
    He'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 ago
      Ok, 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.
almost 18y ago
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...
- frisco 18y ago
  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.
  - KirinDave 18y ago
    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.
    - dhs 18y ago
      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.
codeodor 18y ago
How does one go about showing that there is no way to solve such a problem? What about the argument that perhaps the author was not clever enough to devise an algorithm which solves the problem he stated? Perhaps when I read the papers I will be enlightened?
- cperciva 18y ago
  How does one go about showing that there is no way to solve such a problem? With great difficulty. Usually the approach is to suppose that you have an algorithm and show that either (a) this algorithm allows you to do something impossible (e.g., solve a different impossible problem, or reach a contradiction); or (b) there are two different problems with different answers which the specified algorithm cannot distinguish between (this is generally only possible where you're proving that it's impossible to compute something in less than some number of steps). The first approach is used for things like showing that the halting problem is impossible; the second approach is used for things like showing that it's impossible to have a comparison sort which runs in less than O(N log N) time.
  - codeodor 18y ago
    Actually, now that you mention it I can recall these. Thanks for the refresher!
trjordan 18y ago
Look at it this way: imagine you have a server that's totally maxed out (CPU-bound), 24 hours a day. If you add just one more connection to its load, it won't be able to handle it. No matter how long you give it, it'll just fall further and further behind. The requested pages are uncomputable! A faster computer, on the other hand, will keep up just fine, and finish all the computations. This isn't how computations have been traditionally defined, so that's why it seems so unintuitive. But, he's right nonetheless.
- deleted 18y ago
  [deleted]
- tybris 18y ago
  The server will get further and further behind, but you can not give it work it will never finish.
  - trjordan 18y ago
    Sure, you can. The work is "handle 350 requests per hour".
    - dhs 18y ago
      Turing's computer was an idealized human - to him, computers were humans who did computations for a living - who were granted infinite time and tape - that's the idealization - to solve exactly one problem. Anything that talks about "x problems per hour" has nothing to do with what he said.
    - tybris 18y ago
      Where did you get the time dimension from?
shalmanese 18y ago
Turing machines are constructed in a closed, static universe. This guy says that if you need to deal with a source of changing data, turing results don't apply. This is both obvious and important to state, although not with as much verbiage.
- jerf 18y ago
  Expanding on that, it should also be pointed out that this is well-known as being among the list of assumptions that prevent Turing Machines from working in the real world. We speak of "steps", but they do not have any actual relationship to "time". The tape has no obvious relationship to "space", either. So, right off in the first sentence "I have recently shown that the concept of a Universal Computer cannot be realized.", I thought "well, it's hardly like that's a challenge..." There's actually some interesting theory here, I think, but it's only obscured by being wrapped in rhetoric about Church-Turing being wrong and such. All mathematical theorems include a set of assumptions, and it's not news that if you change the truth of the assumptions the theorems may stop holding.
amalcon 18y ago
Suppose that my "computing device" were a machine designed to build and program more copies of itself. This device would "compute" a function across n variables in time log n by building n-1 copies of itself, and then parallelizing the computation across them. With sufficient resources, this machine could could compute the function for any n in finite time. All the author has done is posit an ever-increasing volume of data, such that the rate at which the volume increases causes it to outpace the speed of the computation. It seems that positing an ever-increasing computational capacity is a reasonable solution to this problem.
- psb217 18y ago
  Your time complexity of log n appears from nowhere. It is entirely possible that the complexity of calculating the original function F was worse than polynomial in the number of variables, in which case a polynomial/linear increase in the number of machines could not reduce the complexity by more than a polynomial/linear factor, thus leaving the computational complexity worse than polynomial (e.g. exponential/super-exponential). I've made a comment further down that posits an idea similar to yours, though with a bit more precision.
stonemetal 18y ago
Isn't this more or less the same issue as multiple infinities. Whole numbers are infinite but countable, but rationals are infinite and not countable. UTMs are able to compute the infinite but there are infinities that are not computable.
- banned_man 18y ago
  Rationals are countable but dense. You can biject Z * Z <-> N trivially (start from origin, spiral out) and Q can be constructed as a subset of Z * Z. Reals are uncountable.
varjag 18y ago
Stopped reading at mention of "physical variable".
smoofra 18y ago
this is crackpotery
antipax 18y ago
Since when was there a minimum amount of time for a theoretical computer to do any number of computations? I suppose that any computer must take some finite, non-zero amount of time to perform an "instruction", because if the amount of time per instruction is zero, that would violate Turing's proof of the undecidability of the halting problem over Turing machines. His idea does have some merit, but I still don't think that this means there cannot be a Universal Computer -- just that it may be something that operates on a level above a Turing machine. I'd imagine it would involve some sort of recursive structure.
forinti 18y ago
I think Peter Wegner made this same point in the paper "Why interaction is more powerful than algorithms" in CACM (Volume 40, Issue 5, May 1997).
- dhs 18y ago
  Yes, interactive computation is proven to be - statistically - more powerful than algorithmic computation - sometimes. It's also "less powerful" some other times, and since it's not computable at which times interaction is "better", it's not a general advantage. But Turing never considered the case of interaction in his definition of computation, so Wegner is talking about something else.
  - forinti 18y ago
    Turing did in fact consider this possibility, and he instinctively knew that a machine that allowed interactions would be more powerful, but he couldn't prove it.
    - dhs 18y ago
      Just to make sure, I searched for "interaction" in "On computable numbers...", and it's not in there. And, like I said, in the general case, interaction is "more powerful" than algorithm as often as it is "less powerful". Edit - Example: You're on "'Who Wants to Be a Millionaire?" You're in "algorithm mode" for most of the questions, but you're granted one "interaction", via a phone call. On the show, you're allowed to call anybody you want, and if you know to call somebody who's really clever, chances are that interaction will be more powerful than computation. But that's not the general case: the general case would be for you to call a random phone number, and chances are that won't help you - so, in that case, not more powerful.
      - forinti 18y ago
        Please look up http://en.wikipedia.org/wiki/Oracle_machine http://en.wikipedia.org/wiki/Oracle_machine. The purpose of a machine with interactions is not to be more intelligent, it is just to be able to execute a larger body of computations than a machine without interactions would. You can't model operating systems on Turing machines, for example, precisely because they need to interact. This is from the Wikipedia entry on Alan Turing: "In June 1938 he obtained his Ph.D. from Princeton; his dissertation introduced the notion of relative computing, where Turing machines are augmented with so-called oracles, allowing a study of problems that cannot be solved by a Turing machine."
joshu 18y ago
http://math.ucr.edu/home/baez/crackpot.html http://math.ucr.edu/home/baez/crackpot.html Do we need a CS equivalent?
milkmandan 18y ago
He basically says that the UTM cannot run a TM in real time, so that makes it non-universal. It's pretty inane.
ggchappell 18y ago
Folks, the only problem with this article is the HN headline. Aki never claims Turing was wrong. And I think he is demonstrating something rather interesting: that time dependence has a significant effect on the power of a computing device.
bcf 18y ago
After reading Mr. Akl's website, I'm reminded of this recent HN post: http://trc.ucdavis.edu/bajaffee/NEM150/Course%20Content/dancing.htm http://trc.ucdavis.edu/bajaffee/NEM150/Course%20Content/danc... Also, I would be interested to hear what Stephen Wolfram has to say about all of this (http://www.wolframscience.com/prizes/tm23/index.html http://www.wolframscience.com/prizes/tm23/index.html).
psb217 18y ago
The way I see it, you could program a Turing Machine MF which has some finite "per-time-step" computation speed _n_, such that MF "knows" the following: 1: The general form/program for solving function F for any arbitrary number, _m_, of variables. 2: How to construct a Turing Machine MF' capable of performing _m_ "operations per-time-step", and programmed with 1. Even in his crazy-town world of redefined computation, the Turing Machine MF is capable of computing any computable function F, of any number of time-varying variables _m_. I.e. given such a function F, MF simply creates a suitable machine MF' and copies the output of MF' to its own output. Thus, MF computes F, albeit by proxy. QED, etc. It's possible that I'm now in some TM dual to his time-varying primal, but whatevs, I can do what I want. ADD: As far as the computability results that I am familiar with are concerned, without loss of generality one could also just assume that all Turing Machines have infinite speed. The necessity of introducing the concept of a "time-step" into the definition of Turing Machines only occurs when computation time is actually of interest. Though, for complexity results one could still assume infinite speed, albeit the number of operations would still need to be counted.

46 points by ewakened 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 ago
Yes that's a better way of putting it :) Thanks.
frisco 18y ago
He's saying though that those two can't be separated -- the functions the machines are computing are themselves changing with time.
- cperciva 18y ago
  the 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 ago
    It 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 ago
      It 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 ago
        Example: 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 ago
        The 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 ago
  Turing 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 ago
But 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 ago
Thank 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 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.)
davidmathers 18y ago
How 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 ago
  He'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 ago
    Ok, 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.

almost 18y ago

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

frisco 18y ago
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.
- KirinDave 18y ago
  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.
  - dhs 18y ago
    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.

codeodor 18y ago

How does one go about showing that there is no way to solve such a problem? What about the argument that perhaps the author was not clever enough to devise an algorithm which solves the problem he stated? Perhaps when I read the papers I will be enlightened?

cperciva 18y ago
How does one go about showing that there is no way to solve such a problem? With great difficulty. Usually the approach is to suppose that you have an algorithm and show that either (a) this algorithm allows you to do something impossible (e.g., solve a different impossible problem, or reach a contradiction); or (b) there are two different problems with different answers which the specified algorithm cannot distinguish between (this is generally only possible where you're proving that it's impossible to compute something in less than some number of steps). The first approach is used for things like showing that the halting problem is impossible; the second approach is used for things like showing that it's impossible to have a comparison sort which runs in less than O(N log N) time.
- codeodor 18y ago
  Actually, now that you mention it I can recall these. Thanks for the refresher!

trjordan 18y ago

Look at it this way: imagine you have a server that's totally maxed out (CPU-bound), 24 hours a day. If you add just one more connection to its load, it won't be able to handle it. No matter how long you give it, it'll just fall further and further behind. The requested pages are uncomputable! A faster computer, on the other hand, will keep up just fine, and finish all the computations. This isn't how computations have been traditionally defined, so that's why it seems so unintuitive. But, he's right nonetheless.

deleted 18y ago
[deleted]
tybris 18y ago
The server will get further and further behind, but you can not give it work it will never finish.
- trjordan 18y ago
  Sure, you can. The work is "handle 350 requests per hour".
  - dhs 18y ago
    Turing's computer was an idealized human - to him, computers were humans who did computations for a living - who were granted infinite time and tape - that's the idealization - to solve exactly one problem. Anything that talks about "x problems per hour" has nothing to do with what he said.
  - tybris 18y ago
    Where did you get the time dimension from?

shalmanese 18y ago

Turing machines are constructed in a closed, static universe. This guy says that if you need to deal with a source of changing data, turing results don't apply. This is both obvious and important to state, although not with as much verbiage.

jerf 18y ago
Expanding on that, it should also be pointed out that this is well-known as being among the list of assumptions that prevent Turing Machines from working in the real world. We speak of "steps", but they do not have any actual relationship to "time". The tape has no obvious relationship to "space", either. So, right off in the first sentence "I have recently shown that the concept of a Universal Computer cannot be realized.", I thought "well, it's hardly like that's a challenge..." There's actually some interesting theory here, I think, but it's only obscured by being wrapped in rhetoric about Church-Turing being wrong and such. All mathematical theorems include a set of assumptions, and it's not news that if you change the truth of the assumptions the theorems may stop holding.

amalcon 18y ago

Suppose that my "computing device" were a machine designed to build and program more copies of itself. This device would "compute" a function across n variables in time log n by building n-1 copies of itself, and then parallelizing the computation across them. With sufficient resources, this machine could could compute the function for any n in finite time. All the author has done is posit an ever-increasing volume of data, such that the rate at which the volume increases causes it to outpace the speed of the computation. It seems that positing an ever-increasing computational capacity is a reasonable solution to this problem.

psb217 18y ago
Your time complexity of log n appears from nowhere. It is entirely possible that the complexity of calculating the original function F was worse than polynomial in the number of variables, in which case a polynomial/linear increase in the number of machines could not reduce the complexity by more than a polynomial/linear factor, thus leaving the computational complexity worse than polynomial (e.g. exponential/super-exponential). I've made a comment further down that posits an idea similar to yours, though with a bit more precision.

stonemetal 18y ago

Isn't this more or less the same issue as multiple infinities. Whole numbers are infinite but countable, but rationals are infinite and not countable. UTMs are able to compute the infinite but there are infinities that are not computable.

banned_man 18y ago
Rationals are countable but dense. You can biject Z * Z <-> N trivially (start from origin, spiral out) and Q can be constructed as a subset of Z * Z. Reals are uncountable.

varjag 18y ago

Stopped reading at mention of "physical variable".

smoofra 18y ago

this is crackpotery

antipax 18y ago

Since when was there a minimum amount of time for a theoretical computer to do any number of computations? I suppose that any computer must take some finite, non-zero amount of time to perform an "instruction", because if the amount of time per instruction is zero, that would violate Turing's proof of the undecidability of the halting problem over Turing machines. His idea does have some merit, but I still don't think that this means there cannot be a Universal Computer -- just that it may be something that operates on a level above a Turing machine. I'd imagine it would involve some sort of recursive structure.

forinti 18y ago

I think Peter Wegner made this same point in the paper "Why interaction is more powerful than algorithms" in CACM (Volume 40, Issue 5, May 1997).

dhs 18y ago
Yes, interactive computation is proven to be - statistically - more powerful than algorithmic computation - sometimes. It's also "less powerful" some other times, and since it's not computable at which times interaction is "better", it's not a general advantage. But Turing never considered the case of interaction in his definition of computation, so Wegner is talking about something else.
- forinti 18y ago
  Turing did in fact consider this possibility, and he instinctively knew that a machine that allowed interactions would be more powerful, but he couldn't prove it.
  - dhs 18y ago
    Just to make sure, I searched for "interaction" in "On computable numbers...", and it's not in there. And, like I said, in the general case, interaction is "more powerful" than algorithm as often as it is "less powerful". Edit - Example: You're on "'Who Wants to Be a Millionaire?" You're in "algorithm mode" for most of the questions, but you're granted one "interaction", via a phone call. On the show, you're allowed to call anybody you want, and if you know to call somebody who's really clever, chances are that interaction will be more powerful than computation. But that's not the general case: the general case would be for you to call a random phone number, and chances are that won't help you - so, in that case, not more powerful.
    - forinti 18y ago
      Please look up http://en.wikipedia.org/wiki/Oracle_machine http://en.wikipedia.org/wiki/Oracle_machine. The purpose of a machine with interactions is not to be more intelligent, it is just to be able to execute a larger body of computations than a machine without interactions would. You can't model operating systems on Turing machines, for example, precisely because they need to interact. This is from the Wikipedia entry on Alan Turing: "In June 1938 he obtained his Ph.D. from Princeton; his dissertation introduced the notion of relative computing, where Turing machines are augmented with so-called oracles, allowing a study of problems that cannot be solved by a Turing machine."

joshu 18y ago

http://math.ucr.edu/home/baez/crackpot.html http://math.ucr.edu/home/baez/crackpot.html Do we need a CS equivalent?

milkmandan 18y ago

He basically says that the UTM cannot run a TM in real time, so that makes it non-universal. It's pretty inane.

ggchappell 18y ago

Folks, the only problem with this article is the HN headline. Aki never claims Turing was wrong. And I think he is demonstrating something rather interesting: that time dependence has a significant effect on the power of a computing device.

bcf 18y ago

After reading Mr. Akl's website, I'm reminded of this recent HN post: http://trc.ucdavis.edu/bajaffee/NEM150/Course%20Content/dancing.htm http://trc.ucdavis.edu/bajaffee/NEM150/Course%20Content/danc... Also, I would be interested to hear what Stephen Wolfram has to say about all of this (http://www.wolframscience.com/prizes/tm23/index.html http://www.wolframscience.com/prizes/tm23/index.html).

psb217 18y ago

The way I see it, you could program a Turing Machine MF which has some finite "per-time-step" computation speed _n_, such that MF "knows" the following: 1: The general form/program for solving function F for any arbitrary number, _m_, of variables. 2: How to construct a Turing Machine MF' capable of performing _m_ "operations per-time-step", and programmed with 1. Even in his crazy-town world of redefined computation, the Turing Machine MF is capable of computing any computable function F, of any number of time-varying variables _m_. I.e. given such a function F, MF simply creates a suitable machine MF' and copies the output of MF' to its own output. Thus, MF computes F, albeit by proxy. QED, etc. It's possible that I'm now in some TM dual to his time-varying primal, but whatevs, I can do what I want. ADD: As far as the computability results that I am familiar with are concerned, without loss of generality one could also just assume that all Turing Machines have infinite speed. The necessity of introducing the concept of a "time-step" into the definition of Turing Machines only occurs when computation time is actually of interest. Though, for complexity results one could still assume infinite speed, albeit the number of operations would still need to be counted.