Re: Poll: Are PCs Turing Machines?

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

Date: Mon, 06 Dec 2004 18:19:31 GMT

"Steven" <steven2000@despammed.com> wrote in message
news:1102324161.599083.147970@f14g2000cwb.googlegroups.com...
>The question is whether the arbitrary behaviour
> of a PC due to user input, mechanical breakdowns, heat deaths of the
> universe and so on can be simulated by a TM. I think of a "real world"
> PC as a hybrid system with an uncountably large state space, and if I
> am not mistaken, a TM can only simulate countably many states? Any
> opinions?
>
> Thanks, S.
>

As I understand it, uncountable always means infinitely uncountable,
whereas countable, can either be finitely or infinitely countable.

The set of all Turing machines is countable. Thus there exists real
numbers that can not be accepted by any Turing machine.
"A Turing machine is a kind of state machine. At any time the machine is in
any one of a finite number of states. Instructions for a Turing machine
consist
in specified conditions under which the machine will transition between one
state and another." The formal definition of a finite state machine is that
it has
a countable number of (thus discrete) states.

I think because there are real numbers that a digital computer does not
accept (but truncates) that a digital computer also has a countable number
of states. Maybe this isn't the best reason, a continuous vs. discrete
criteria,
and will be expounded upon by other posters.

Regards,
Stephen

Relevant Pages

  • Re: What evidence is there that a neuron is digital computer ?
    ... our brain can compute like a turing machine, because we can make all the ... Turing Computability With Neural Netshttp://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.47.8383 ... doesn't seem to make any sense because the system is not even discrete, ...
    (comp.ai.philosophy)
  • Re: Poll: Are PCs Turing Machines?
    ... > PC as a hybrid system with an uncountably large state space, ... "A Turing machine is a kind of state machine. ... I think because there are real numbers that a digital computer does not ... Maybe this isn't the best reason, a continuous vs. discrete ...
    (sci.math)
  • Re: Question on Chaitin
    ... >> I've tried to correct some of your ignorant claims about philosophy ... modeled as, a digital computer or Turing machine, is too vague to apply ... undermined by the incompleteness theorems. ... There is no question of what set a given Turing machine ...
    (sci.logic)
  • Re: Is memory-based reasoning more powerful than Turing machine?
    ... information, then Turing machines, LUTs, and circuits are all equally ... too many such functions to be encoded by a digital computer. ... But it's not clear to me how a Turing machine can do ... Notice that if a memory-based reasoner is more powerful than a Turing ...
    (comp.theory)