On 9/30/2011 6:25, Invisible wrote:
> Now consider a simple digital computer. It might have only one binary adder
> circuit, and yet it can add up an unlimited number of operands, with
> unlimited precision.

Except that a Turing machine has an unbounded amount of memory, so you're 
not really comparing apples to oranges here.

> Analogue computer: More steps = more hardware.
> Digital computer: More steps = more time.

The digital computer requires more hardware too, in terms of "tape". All 
those numbers you're adding have to be in the input somewhere.

> That's a fundamental difference. If I have an analogue computer with ten
> adder circuits, I cannot add up eleven numbers. But if I have a
> Turing-complete machine, I can add up an /unlimited/ number of operands. You
> never need more hardware. It just takes more time.

You never need more hardware because, by definition, Turing machines have 
unbounded amounts of hardware attached. If you had an unlimited number of 
analog ALUs, you'd be golden with an analog computer.

> Also, you can often "program" an analogue computer. But you basically do
> that by rewiring it. The machine can't rewire itself. But a Turing-complete
> machine can have self-modifying code.

You do it by rewiring a Turing machine, also. It just so happens that 
because you have an unlimited amount of memory, you can wire up one computer 
that will simulate whatever other computer you put in the memory units 
(i.e., the "tape"). You could do the same with an analog computer as well.

> Actually /proving/ that something is Turing-complete is usually not simple

It's usually not too hard. You just write a turing-machine simulator in 
whatever system you're trying to prove is turing complete. If you can 
simulate a turing machine with an analog computer, then that analog computer 
is turing complete.

-- 
Darren New, San Diego CA, USA (PST)
   How come I never get only one kudo?

Post a reply to this message