On 30/09/2011 2:25 PM, Invisible wrote:
>>> Now, how the heck you formulate that into some kind of coherent
>>> definition......
>>
>> When you do, submit it as a PHD thesis. ;-)
>
> Thanks. I'll pass.
>

LOL



>> alter its input or operating instructions or what?

>> for each problem they needed to solve. But it could be done.
>
> 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.

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

> Actually /proving/ that something is Turing-complete is usually not
> simple at all. But probing that something /isn't/ Turing-complete just
> requires you to find one thing that it can't do [and a Turing-complete
> machine can].
>
> You could say it's a calculator if it only calculates one thing (e.g., a
> mechanical tide predictor), it's a calculator construction kit if it can
> calculate many things (e.g., a typical "programmable" analogue
> "computer"), and it's a computer if it's Turing-complete (i.e., it has a
> stored program, decision-making capabilities, etc.)
>
Hmm! I don't know. You can do some very intricate and complicated things 
with analogue electronics. Consider the brain. O_o

-- 
Regards
     Stephen

Post a reply to this message