What computer science theorem is this? [closed]

Question

Closed. This question does not meet Stack Overflow guidelines. It is not currently accepting answers.

---

This question does not appear to be about programming within the scope defined in the help center.

Closed 8 years ago.

Improve this question

I've got a study note from about ten years ago where I've written:

All the power of programming is available in any language that supports three things:

step by step execution (statements)

altering the flow of execution based on conditions (branch selection)

performing an execution repeatedly in a loop.

I have three questions:

1) Who first postulated this?

2) Who first proved it? (I remember the proof is relatively recent.)

3) What popular book or text was my most likely source for this?

Googling hasn't given me any answers. :-(

Answer 1

You are thinking of the Structured Program theorem, which demonstrates that a language with those features can compute any computable function.

As Wikipedia states, it was stated in this form by Corrado Böhm and Giuseppe Jacopini in 1966, but can be traced back further to regular languages.