|
|
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
|
|
|
|
Darren New wrote:
> 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.
...ignoring for a moment such minor details as "efficiency" and "easy of
use" that are of no consequence to mathematicians who have theoretical
machines with infinite RAM capacity available to them. ;-)
Post a reply to this message
|
|