Apologies for being out of touch with the list, I can only dip a toe
in occasionally these days.
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.domain.name.hidden
To unsubscribe from this group, send email to everything-list-unsubscribe.domain.name.hidden
For more options, visit this group at
http://groups.google.com/group/everything-list
-~----------~----~----~----~------~----~------~--~---
Received on Fri Jul 21 2006 - 18:53:02 PDT