Re: Stupid question: Infinitely many equivalent TMs?



pietromas@xxxxxxxxx wrote:
Stupid question Im sure, but is it true to say that there are
infinitely many ways to imlement any algorithm? I mean, given a Turing
Machine, I can just add <move left, move right> pairs ad-infinitum to
create a new machine with the same behaviour right?

Yes, depending on exactly what you mean by "same behavior."

And if this is the case, who does I site when I say that there are
infinitely many ways of implementing any algorithm.

Generally, one doesn't need to cite the obvious. Depending on your
intended audience, you may wish to include the reasoning you used
in your first paragraph.


Regards,

Rick

.

Relevant Pages

  • Stupid question: Infinitely many equivalent TMs?
    ... Stupid question Im sure, but is it true to say that there are ... infinitely many ways to imlement any algorithm? ... I mean, given a Turing ... infinitely many ways of implementing any algorithm. ...
    (comp.theory)
  • Re: misconceptions on computer science
    ... >> Show me an algorithm that is beautiful but useless. ... You haven't given a single example that furthers your position. ... >> What specific thing that Turing did are you talking about? ... Because those sound like engineering projects to me. ...
    (comp.object)
  • Re: No Set Contains Every Computable Natural (was Church-Turing compared to Zuse-Fredkin thesis)
    ... Russell is right about Turing saying this, ... You might not want to call this an algorithm which has ... decimal representation of x digit by digit. ...
    (comp.theory)
  • Re: Quantum computer using using artificial atoms.
    ... >> get a quantum polynomial time algorithm to run in polynomial time on ... > Factoring has never been proven to be a hard problem, ... Every important factoring algorithm ... > others who are trying to push the idea that quantum Turing is different ...
    (sci.crypt)
  • Re: Turing Machines and Physical Computation
    ... rather than adumbrated in that 1936 Turing paper On Computable ... ... any actual computer has finite memory, ... computer will run out of memory for some huge calculation. ... It is generally assumed that an algorithm must satisfy the following ...
    (sci.math)