5 ms·

Worst case scenario, one machine can emulate the other machine, running that input. Therefore an upper bound on one machine can be used to derive an upper bound

• btilly 16y ago
  However, you must also have a proof about the complexity of the emulation and the encoding of programs to emulate. Without that proof - which basically means you are no longer talking about two arbitrary machines but rather about two which are deeply related - the mere possibility of emulation tells you nothing other than that one machine is of equal or greater computational power than the other. If we're talking about Turing machines, all of the machines are of equal computational power, and are also able to emulate each other. If we're talking about real machines, the take away is that moving from one machine to the other doesn't require much code, but does require that the other machine be powerful enough. Thus leading to Ray Kurzweil's argument that the real challenge is getting a powerful enough machine, and not in the amount of code needed to run on that machine. (He further argues that Moore's law will provide us with that machine.) And, maybe I need another cup of coffee but I am actually having trouble parsing the syntax of your comment about Omega. Basically I was saying that if you offer some facility to translate programs from machine A to machine B, only a very small portion of the programs on machine B will turn out to be programs that were translated from machine A. Therefore the probability of programs halting on machine A tells us nothing about what the majority of programs on machine B are likely to do, and therefore tells us very little about the probability of a random program on machine B halting. Does that make more sense?
  • dasht 16y ago
    If we're talking about Turing machines, all of the machines are of equal computational power, and are also able to emulate each other. We aren't necessarily talking about Turing machines but let's suppose that we are. We're talking about machines powerful enough to compute anything that any Turing machine can compute. You are correct that any one of these machines can emulate any of the others. What's relevant to Kurzweil's argument is two-fold: If I tell you about Turing-class machine A and give you Turing-class machine B, we know right away that you can write an A emulator that runs on B. We know that because they are both Turing class. What we don't know is how big that emulator program is. It might take a trillion lines of code just to write the emulator. Next, I have told you about machine A but now I also give you a 50 Megabyte program (called "GENOME") that runs on machine A. Now you must write your emulator, encode GENOME for your emulator, and run it on B. We know you can do that since these are both Turing class machines. What we do not know is how many bits it will take to encode GENOME. It could be 50 Megabytes. Or it could be 50 Terabytes. You just can't tell without proving things about the specific details of machines A and B and your emulator. Kurzweil makes an argument analogous to "Hey, GENOME only takes 50MB on machine A. There's no way it takes 50TB on machine B. Information theory at work, man! Use your head!" Problem is, "information theory" says no such thing. Actually, it says "If that's all we've been told, hell it could easily take 50TB on machine B. It could take 5 bytes. Who knows? There's not enough said about machines A and B or the program GENOME to tell!" Basically I was saying that if you offer some facility to translate programs from machine A to machine B, only a very small portion of the programs on machine B will turn out to be programs that were translated from machine A. Therefore the probability of programs halting on machine A tells us nothing about what the majority of programs on machine B are likely to do, and therefore tells us very little about the probability of a random program on machine B halting. Yes. You are correctly observing that Omega is not really a constant - it is a class of constants. For machine A there is Omega_A. For machine B, Omega_B. That is why Chaitin lectures about Omega but only after several reminders that it's really "Omega_X for some specific machine X -- but I'm mostly just going to say Omega and let X be understood." So, now, think that through with Kurzweil goggles on. In Kurzweil's world, a program of 50MB on one machine can't be 50TB on the next machine -- that's just silly, right? Well, if he were correct then, in general, Omega_A and Omega_B, for any machines A and B, would have to be somewhat close in value. We know that Omega_A and Omega_B don't have to be close (other than that they both come from the same (0,1) interval). By contradiction we conclude that we don't live in the world Kurzweil is describing.
• kragen 16y ago
  > sure, our fancy big super computer from IBM can emulate the zygote (let's say) but.. what's that gonna take? Well, you know, part of the other half of the "source code" in the genome explains how to build a zygote. It doesn't explain how to build a universe, but there's no particular reason to believe that the universe is designed to make zygotes easy to build. The encoding scheme isn't particularly problematic; it's a constant factor on the efficiency, and a small additive increment to the source code.