Apologies for being out of touch with the list, I can only dip a toe in occasionally these days.

## Advertising

Stathis wrote: > It seems to me trivially obvious that any sufficiently complex physical > system implements any finite computation, just as any sufficiently > large block of marble contains every marble statue of a given size. > The difference between random noise (or a block of marble) on the one > hand and a well-behaved computer (or the product of a sculptor's work) > on the other is that the information is in the latter case presented > in a way that can interact with the world containing the substrate of > its implementation. But I think that this idea leads to almost the same > conclusion that you reach: it really seems that if any computation can > be mapped to any physical substrate, then that substrate is superfluous > except in that tiny subset of cases involving well-behaved computers that > can handle counterfactuals and thus interact with their environment, > and we may as well say that every computation exists by virtue of its > status as a platonic object. I say "almost" because I can't quite see > how to prove it, even though I suspect that it is so. If we take the next step, though, the real question changes somewhat. Let's imagine that what we see as physical objects are actually the result of some kind of computational process. We are living in a virtual universe. Even if you don't believe it, try following the logic for a minute. In that case, this physical object, this block of marble, is actually a computational process. But if we continue to believe that the complex "physical" system implements every computation, then what we are really saying is that a complex "computational" system implements every computation - because the complex physical system is actually (or at least, hypothetically could be) a manifestation of a computation. So we should really reword Stathis claim. Instead of "any sufficiently complex physical system implements any finite computation", it must be, "any sufficiently complex computation implements any finite computation". And IMO that is a rather more interesting claim, and perhaps more amenable to analysis since it stays within the realm of mathematics and logic, rather than crossing boundaries between the physical and the ideal. Indeed, it is not inherently surprising or implausible that a computation can be said to implement more than one computation. If we think of a computation as a sequence of logical steps A, B, C, ... Z, then it automatically can be said to also implement every subsequence of those steps: for example, "J, K, L" is implemented by that sequence, as is "O, P, Q, R, S, T". It might also be that computation A could be embedded in computation B in a more subtle way. We could, for example, interleave the computations of A and B, doing A's operations on the odd-numbered steps and doing B's operations on the even-numbered ones. With Stathis' "sufficiently complex" computations, we could imagine that the computation is so long and so messy and confusing that, with enough work, we could indeed hope to find virtually any smaller computation embedded within this complexity. On the other hand it clearly won't do to say that every computation implements every other. The identity computation F(x) = x does not implement a master-level chess playing program. So there must be a threshold of complexity before we could start making this kind of claim. This raises the question of whether there is an objective fact about whether computation A implements computation B. And should it count if A merely comes "close" to implementing B? There is a paradox due to Putman which argues that even a counting program "loop: x = x + 1; goto loop;" will implement every program. Going back to my first example of some program that goes through 26 steps or states A through Z, we can identify the initial state of the counting program x=1 with state A; we identify x=2 with state B, and so on up through x=26 which is state Z. So our counting program can be said, in a sense, to implement our A-Z program, if we interpret it the right way. Then there are various responses to this, and counter-arguments as well, which I won't get into. IMO there is a gray area where it is hard to say whether A truly implements B or if the correspondence is in the mind of the beholder. The relevance to our issues is when we start talking about measures over computer programs and computations, and relating them to first-person experiences, it's necessary to consider whether it is meaningful to say what a given computation is doing. If every sufficiently complex computation implements every other, then that contradicts any reasoning based on the differences between different computations. So I think it is an important issue to get right and to be clear about. Hal Finney --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Everything List" group. To post to this group, send email to everything-list@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/everything-list -~----------~----~----~----~------~----~------~--~---