On 30/09/2011 05:53 PM, Darren New wrote:
> 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.

Yeah, one of the details I glossed over.

If I have a normal desktop PC then /in principle/ I can insert an 
endless number of disks into it. Obviously, a Turing machine is a 
mathematical abstraction. No physical machine can have infinite 
anything, because the universe is finite.

> 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.

Small difference: ALUs require energy. A storage medium typically doesn't.

>> 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.

If you're saying "you could make an analogue computer that was 
Turing-complete" then, yes, of course you could. If you're saying "the 
analogue computers what people actually built were Turing-complete" 
then, no, not really...

>> 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.

Exhibit A: Totallistic cellular automaton number #110.

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message