Re: Poll: Are PCs Turing Machines?

From: Stephen Harris (cyberguard1048-usenet_at_yahoo.com)
Date: 12/04/04 

Date: Sat, 04 Dec 2004 00:07:39 GMT

"Mark Nudelman" <markn@greenwoodsoftware.com> wrote in message
news:9A6sd.138625$5K2.42126@attbi_s03...
> Eray Ozkural exa wrote:
>> "Mark Nudelman" <markn@greenwoodsoftware.com> wrote in message
>> news:<BCKrd.600129$mD.87873@attbi_s02>...
>>> Eray Ozkural exa wrote:
>>>> examachine@gmail.com (Eray Ozkural exa) wrote in message
>>>> news:<320e992a.0412011208.2b75bc@posting.google.com>...
>>>>> I wonder what people really think about this.
>>>>>
>>>>> Are PCs physical examples to Turing Machines? [*]
>>>>>
>>>>> Please write only Yes/No to avoid discussion.
>>>>
>>>> A clarification is in order.
>>> ...
>>>> We usually consider equivalence in computability to be a sufficient
>>>> condition for being a physical example to a model of computation,
>>>> essentially covering the capabilities of "causal mechanism"
>>>> involved.
>>> ...
>>>> It may be regarded sufficient that we can find a TM counterpart to
>>>> everything essential to computation in a PC, and the other way
>>>> around.
>>>
>>> Still "no".
>>>
>>> A TM can perform a calculation that requires 10^1000 storage cells,
>>> but no PC or any other physical computer could do that.
>>
>> Hi Mark,
>>
>> There is another reading comprehension problem involved. Wearing the
>> philosopher hat, I think I should have made this one clear as well:
>>
>> I do not ask the following:
>>
>> Is the set of all PCs computationally equivalent to the set of all TMs
>> (whatever that means)
>>
>> I ask:
>> Given a PC. Is it computationally equivalent to *a* Turing Machine?
>>
>> That's a completely different question. I suggest you to consider the
>> latter reading, which is the correct reading.
>
> Well, when you said
>>>> It may be regarded sufficient that we can find a TM counterpart to
>>>> everything essential to computation in a PC, and the other way
>>>> around.
> the phrase "and the other way around" pretty much precludes the
> interpretation that you're now proposing.
>
> But if you're now asking, for each PC, is there a compuatationally
> equivalent TM, then the answer is yes.
> If you're asking, for each TM, is there a computationally equivalent PC,
> the
> answer is no.
>
> --Mark
>

Hi,

I have noted your perspicacious remarks. I think the finiteness
of matter is tied to the physical constraint on memory of a PC.
But the older theory which preceded the Big Bang, Steady State says:

At first glance this seems to imply we must abandon the idea that the
Universe could be unchanging. However this is not necessarily so, because of
one rather exceptional kind of expansion that can occur if the Einstein
Field Equations are modified appropriately. This is when the Universe is
always expanding, but the rate of expansion and the density of matter are
always the same. Clearly this

requires a continuous creation of matter to keep the density constant while
the Universe continually expands. Such a universe is called a Steady State

Universe . For many people this is an attractive possibility, because an
unchanging Universe is thought to be "more perfect" than a changing one
[79]. However this model cannot explain evidence obtained from optical and
radio telescopes that there was a higher density of radio sources and
quasars in the past than at present (the densities would have to be
unchanging, if the Universe were in a steady state, for then conditions
would be the same everywhere); and it does not give a natural explanation of
the cosmic background radiation (discussed below). It has therefore been
abandoned by almost all cosmologists.

SH: In the present theory, Big Bang, the density remains the same, and heat
death eventually stops any conversion of energy to mass. There is
experimental evidence that the Big Bang theory is true, while the older
conjecture of the Steady State universe of newly created matter was such a
small amount that it could not be detected by physical experiment to provide
evidence for the SST.

That is why I told Eray he would need a Nobel prize in order to plausibly
advance his notion that there is an unlimited supply of matter to store the
ever greater calculations of a PC so there is some sort of equivalence to an
unlimited tape, both capable of ever greater finite computation.

This made me think that there is another aspect of the TM which is
non-physical, dealing with time. Suppose there is newly created matter which
can be utilized by the physical PC. How could a physical calculation proceed
in a coherent manner when the best physical speed of operation would be the
speed of light. Also, besides the idea of the universe expanding forever,
providing new matter/memory if we adopt SST, is the factor that the
expansion is also supposed to accelerating. Which means there is no physical
way for the physical calculating signal to connect to newly created matter
in the universe which is going accelerated expansion away from our galaxy. I
think this is basically the same idea that light which travels at a finite
speed will never reach us from accelerated expanded region of the universe
even if the light travels from that region an infinite length of time.

I decided to run this musing by you just in case my physics was mistaken and
because I thought you might enjoy further speculation on physical
constraints which distinguish an abstract TM from a physical PC.

Best regards, Stephen