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$
6
  • $\begingroup$ Ah, tricksy - intermediate results. That disposes of the BubbleSort/QuickSort example. Have you looked at Hoare Logic? $\endgroup$ Commented Oct 31, 2014 at 20:36
  • $\begingroup$ no idea what you are suggesting. $\endgroup$
    – Tim
    Commented Oct 31, 2014 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
    Commented Mar 13, 2015 at 2:21
  • $\begingroup$ What is your book? @greybeard $\endgroup$
    – Tim
    Commented Mar 13, 2015 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
    Commented Jun 16, 2015 at 9:33

1 Answer 1

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 and acknowledge you have read our privacy policy.

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