Re: Poll: Are PCs Turing Machines?

From: Mark Nudelman (markn_at_greenwoodsoftware.com)
Date: 12/04/04 

Date: Fri, 03 Dec 2004 23:23:49 GMT

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

Relevant Pages

  • Re: Poll: Are PCs Turing Machines?
    ... >>A TM can perform a calculation that requires 10^1000 storage cells, ... >>PC or any other physical computer could do that. ... > There is another reading comprehension problem involved. ...
    (comp.theory)
  • Re: Poll: Are PCs Turing Machines?
    ... >>A TM can perform a calculation that requires 10^1000 storage cells, ... >>PC or any other physical computer could do that. ... > There is another reading comprehension problem involved. ...
    (sci.math)
  • Re: Poll: Are PCs Turing Machines?
    ... >> A TM can perform a calculation that requires 10^1000 storage cells, ... >> but no PC or any other physical computer could do that. ... > There is another reading comprehension problem involved. ... If you're asking, for each TM, is there a computationally equivalent PC, the ...
    (sci.math)
  • Re: Poll: Are PCs Turing Machines?
    ... >> A clarification is in order. ... >> It may be regarded sufficient that we can find a TM counterpart to ... > PC or any other physical computer could do that. ... There is another reading comprehension problem involved. ...
    (sci.math)
  • Re: Poll: Are PCs Turing Machines?
    ... >> A clarification is in order. ... >> It may be regarded sufficient that we can find a TM counterpart to ... > PC or any other physical computer could do that. ... There is another reading comprehension problem involved. ...
    (comp.theory)