>> The formal definition of Turing-completeness is abstract and technical.
>> Essentially Alan Turing proved two main things:
>>
>> 1. It is possible to build *one* machine that can perform *any* possible
>> calculation.
>>
>> 2. Some calculations are impossible.
>>
>> [Simplifying wildly, of course.]
>>
>> You would think that a more complex, more sophisticated machine would be
>> able to calculate more things than a simpler machine. In fact, it turns
>> out that if they are both Turing-complete, they can both calculate
>> exactly the same stuff. (The more sophisticated machine is probably much
>> /faster/, of course...)
>>
>
> Thanks
>
>> Consider an analogue computer, for a moment. It might have circuits that
>> can add numbers together. But if I want to add up one million operands,
>> I need to wire together [at least] one million adder circuits.
>>
>> 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.
>>
>> Analogue computer: More steps = more hardware.
>> Digital computer: More steps = more time.
>>
>> 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.
>>
>> This difference comes about mainly because a digital computer has a
>> /memory/. It can /store/ operands and feed them through its arithmetic
>> circuits one at a time. An analogue computer can't do that, so it has to
>> have one dedicated circuit for each step of the process. A digital
>> computer can /reuse/ the same circuits again and again for different
>> steps, because the steps won't happen all at once.
>>
>
> Not so, an analogue machine can have memory. A capacitor will store a
> voltage until another arithmetic step is added to it. So that argument
> does not hold water.

I was under the impression that a capacitor only holds its charge for a 
very short period of time.

Regardless, have you ever actually seen an analogue computer with 
independently addressable memory cells? I haven't heard of such a thing.

>> 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.
>
> That makes more sense to me.

On the other hand, if the connections were controlled by an array of 
relays or something, and the computer could control the relays... then 
you would be progressing towards a more truly programmable system.

> Hmm! I don't know. You can do some very intricate and complicated things
> with analogue electronics. Consider the brain. O_o

Well, strictly speaking, every digital computer is also an analogue 
computer. They're just designed and used differently.

Post a reply to this message