0
$\begingroup$

An algorithm is a finite sequence of operations on an abstract machine. (Correct me, if I am not correct).

If two algorithms can take the same set of inputs, and for each input, they generates the same sequence of intermediate and final results/output, are they the same algorithm?

What I am thinking is if an algorithm can be thought of just as a mapping from the set of inputs to the set of sequences of intermediate and final results/output.

Thanks.

$\endgroup$
  • $\begingroup$ Ah, tricksy - intermediate results. That disposes of the BubbleSort/QuickSort example. Have you looked at Hoare Logic? $\endgroup$ – outis nihil Oct 31 '14 at 20:36
  • $\begingroup$ no idea what you are suggesting. $\endgroup$ – Tim Oct 31 '14 at 20:43
  • $\begingroup$ I never was entirely easy with the very similar definition of algorithm over at stackoverflow, my take running more like An algorithm is a finite specification of steps to solve a problem. If correct, it does define a solution, if the sequence of steps isn't necessarily finite, correctness is partial. - And there is one of the problems: what if the sequence of intermediate states is infinite? In my book, the algorithms are the same, and (as?) any means of specifying what that next state shall be is equivalent, including specifying how to achieve it. $\endgroup$ – greybeard Mar 13 '15 at 2:21
  • $\begingroup$ What is your book? @greybeard $\endgroup$ – Tim Mar 13 '15 at 2:53
  • 2
    $\begingroup$ Please define "same". Is one dollar the same as another dollar? Is one molecule of water the same as another? Is a boaon the same as another? Is a language the same as its homomorphic image via a renaming homomorphism? $\endgroup$ – babou Jun 16 '15 at 9:33
2
$\begingroup$

Starting with a vague definition of algorithm, you won't get a clear-cut answer. Here are two possible ways to look at it.

  • Algorithms are high-level constructs, that is we distinguish idea from implementation. In that sense,

    for ( i=1; i<n; i++ ) {
      print i
    }
    

    and

    i = 1
    while ( i < n ) {
      print i
      i++
    }
    

    are implementations of the same algorithm, but clearly not the same program. And while this simple example may actually translate to the same machine code for many real languages, it's clear that they don't have to. So whether the programs create the same sequence of states depends on your machine model.

    This is a hint that tying your notion of algorithm to a specific machine model is probably not useful.

  • Algorithms are specific sequences of instructions for fixed machine models. Then, the answer depends on your machine model.

    1. If there is exactly one statement for every possible state change, then a sequence of states induces a unique sequence of statements. Hence, if all inputs cause identical state sequences, the algorithms/programs are the same.

    2. If multiple statements can cause the same state change, then the opposite is true.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.