Warp wrote:
> Darren New <dne### [at] sanrrcom> wrote:
>> Orchid XP v7 wrote:
>>> Since you can build a Turing machine for any possible algorithm, 
> 
>> Or, more precisely, the word "algorithm" is defined (at least in these 
>> realms) as "those calculations for which a Turing machine can be 
>> designed to perform."
> 
>   That sounds a bit like a circular definition. "A turing machine is
> something which can perform any algorithm." "An algorithm is something
> which a turing machine can perform."

Turing machines aren't defined as "something that can perform any 
algorithm." They're defined in terms of state machines and processing 
rules and so on. *Then* you say "algorithms are what Turing machines 
calculate."

What isn't part of the algorithm? The interpretation of the results, for 
example, such as "are orange spots on the tape supposed to be ones or 
zeros?" Putting the program on the Turing machine in the first place, 
for example. I/O capabilities of the system, for example. Analog 
devices, for example. Non-pseudo Randomness, for example.

Why does anyone care? Because if you can simulate any arbitrary TM with 
your specific TM, then you have a Universal TM, which proves that there 
exists a single program that can calculate any algorithm. Why do you 
care about *that*? Because if you can write a simulation of a Universal 
TM in BASIC, then you can prove that BASIC is theoretically as powerful 
as any other machine that can be simulated by a TM.

-- 
   Darren New / San Diego, CA, USA (PST)
     Remember the good old days, when we
     used to complain about cryptography
     being export-restricted?

Post a reply to this message