algorithmtheorytheorem

Böhm-Jacopini theorem

According to Böhm-Jacopini theorem, an algorithm can be written using only three statements:

Lots of teachers, assumes that theorem as an act of faith, and they teach to not use (goto, jump, break, multiple return, etc...) because these instructions are evil.

But when I ask for an explanation, no one is able to provide a proof of theorem.

Personally I don't think that the theorem is false, but I think that it's applicability in real world is not always the better choice.

So I've done a my little search, and these are my doubts:

  1. The theorem has been proven on induction on the structure of the flow chart, but it's really applicable in a computer program?
    According to wikipedia "Böhm and Jacopini's was not really practical as a program transformation algorithm, and thus opened the door for additional research in this direction".

  2. A consequence of theorem prove that each "goto" can be translated into selection or iteration by induction, but what about efficiency? I can't find any proof shows that each algorithm can be rewritten preserving the same performance.

  3. Recursion, a recursive algorithm can really be written using only sequence, selection and iteration? I know that some recursive algorithms can be optimized as loops (think to tail recursion), but can really be applicable to all?

  4. Clean code, I know that an abuse of jumps can create a monstrous code, but I think in some case a correct use of break in a loop can improve the code readability.

Sample:

n = 0;
while (n < 1000 || (cond1 && cond2) || (cond3 && cond4) || (cond5 && cond6)) 
{  
   n++;  
   //The rest of code  
}

Can be rewritten as :

for (n = 0; n < 1000; n++)
{
   if (cond1 && cond2) break;
   elseif (cond2 && cond3) break;
   elseif (cond4 && cond5) break;
   elseif (cond6 && cond7) break;
   //The rest of code
}

Personally I think that the theorem has not been created for write better code, and the idea that a clean code must follow this theorem has been spread into world for a strange subjective reason.

  1. I found this interesting article : https://www.cs.cornell.edu/~kozen/papers/bohmjacopini.pdf I think this prove that real program must not be forced to follow the Jaopini Theorem.
    Do you share the same conclusions?

Summarizing the question, I need to know if a program that uses only (sequence, selection and iteration) is really better than any other that uses different statements, and if there are proves or if it's all subjective.

Solution

  • The theorem has been proven on induction on the structure of the flow chart, but it's really applicable in a computer program? According to wikipedia "Böhm and Jacopini's was not really practical as a program transformation algorithm, and thus opened the door for additional research in this direction".

    The operations and structure they give can easily be shown capable of replicating the function of a Turing machine. As such, it is a Turing-equivalent system of computation. By the Church-Turing thesis, this is believed to be as much computation as we can do: goto would add nothing that is not already possible.

    A consequence of theorem prove that each "goto" can be translated into selection or iteration by induction, but what about efficiency? I can't find any proof shows that each algorithm can be rewritten preserving the same performance.

    Performance is very likely worse for many algorithms without the use of computed goto. You can certainly show it is the case for specific problems. Whether this changes the asymptotic complexity or not is another question but not one Bohm and Jacopini have to do with as far as I am aware.

    Recursion, a recursive algorithm can really be written using only sequence, selection and iteration? I know that some recursive algorithms can be optimized as loops (think to tail recursion), but can really be applicable to all?

    Since Bohm and Jacopini's system is Turing equivalent, then you are correct, recursion adds no new power. It may certainly add readability.