1
$\begingroup$

The structured program theorem proofs Turing-completeness of structured programming, resp. of any programming language that includes sequences, selection (IF) and conditional loops (WHILE).

I am wondering why are selections necessary for the proof as they can be simulated via loops:

IF a:
  <subprogram>

is equivalent to

x := a
WHILE x:
  <subprogram>
  x := false

Am I missing something?

$\endgroup$

1 Answer 1

1
$\begingroup$

I don't think there is anything wrong with your reasoning. I don't think selections (if statements) are necessary, as you prove.

So why is the theorem stated that way? Here comes some speculation on my part. My impression is that the purpose of the theorem was to prove something about a proposed paradigm, structured programming, and structured programming as proposed did include selections (if statements). I don't think anyone was proposing programming without if statements, so there was no need to prove a theorem about programming without if statements.

$\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.