Re: Poll: Are PCs Turing Machines?

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

Date: Sat, 18 Dec 2004 23:01:08 GMT

"|-|erc" <h@r.c> wrote in message news:32hqvlF3n0keuU1@individual.net...
> "Fabian Mueller" <fabim@web.de> wrote in
>> Hi!
>>
>> > Are PCs physical examples to Turing Machines? [*]
>> >
>> > Please write only Yes/No to avoid discussion.
>>
>> As you can see, answering only 'yes' or 'no' does not avoid discussions
>> ;-)
>> So I'll answer a little more:
>> PCs are not physical examples to TMs. A TM has one (or more) infinite
>> band on which it is able to write and read. This would mean a PC should
>> have infinite memory.
>> Another difference is, that a PC can write/read a bigger number of bits
>> (normaly 32) per cycle. I know that this argument does not count much,
>> because using a kind of compression (new alphabet) on a TM would give
>> the TM the same power.
>> But following this, PCs are more a physical example to the so called
>> RAMs (random access machines). To enjoy with care, because those are
>> able to add/operate arbitrarily long words in one cycle. The theoretical
>> model of the function RAMs is much more like the function of PCs than
>> the function of TMs is.
>>
>> Fabian
>
> Right! The PC is NOT a good example of a TM. But it IS a TM.
>
> The PC is a generic finite-memory function evaluator. This is a
> particular algorithm (class).
> All algorithms can be handled by a TM.
>
> Is a set of traffic lights an automation? Yes but an automation can be
> much more powerful.
>
> Is a PC a TM? Yes but a TM can be much more powerful.
>
> The PC is not a UTM, but is is equivalent to a particular TM.
> Tricky subject title!
>
> Herc
>
>

Some PCs can compute the same problems that a TM can compute.

But that is not the question asked in the subject which due to the
sentence structure asks

Do all PCs have a TM correspondence and I've already seen you
answer the question no.

You converted the question in the subject, to a singular

Is there a (or even some) PCs equivalent to TMs?
The answer is yes.

But the person who originally asked the question insists
that there is a PC match for every possible TM.

Also you have converted the question to what class of
problems can be computed for the comparison.

The way the question is actually worded the answer
is entirely no, because TMs are defined as non-physical
and PCs are defined as physical.

The question does not ask if a TM were physically
constructed, without the endless tapes, but a some
physical substitute for the tape's memory function,
would PCs in that case be TMs computationally.
Yes, in that sense because they would both be
finite state machines.

The question is deliberately tricky because the author
is trying to confuse the issue by rewording his earlier
lunacy so that he can say 'this is what I really meant'.

But that PCs could compute some part of the range
of TMs had already been pointed out to the OP
before he posted this desperate escape mechanism.
I use that terminology because Eray is a simpering
arrogant useless nutcase who has managed to
waste the time of his superiors before his pretending
to have some knowledge was exposed as a lie.
It is too bad he was not incarnated as a baby seal.

Relevant Pages

  • Re: Lambda Calculus and Turing Equivalence
    ... >harrisq@tcs.inf.tu-dresden.de (Mitch Harris) wrote in message ... >> Not to jump on the bandwagon, but PCs are not TMs. ... has difficulties in modelling unbounded memory. ...
    (comp.theory)
  • Re: Lambda Calculus and Turing Equivalence
    ... >harrisq@tcs.inf.tu-dresden.de (Mitch Harris) wrote in message ... >> Not to jump on the bandwagon, but PCs are not TMs. ... has difficulties in modelling unbounded memory. ...
    (sci.math)
  • Re: Poll: Are PCs Turing Machines?
    ... >> PCs are not physical examples to TMs. ... A TM has one infinite ... The question is deliberately tricky because the author ...
    (comp.theory)
  • Re: Poll: Are PCs Turing Machines?
    ... >> There is another reading comprehension problem involved. ... >> Is the set of all PCs computationally equivalent to the set of all TMs ... Eray doesn't grasp this. ...
    (comp.theory)
  • Re: Poll: Are PCs Turing Machines?
    ... >> There is another reading comprehension problem involved. ... >> Is the set of all PCs computationally equivalent to the set of all TMs ... Eray doesn't grasp this. ...
    (sci.math)