構造化定理
構造化定理（Structure theorem）、構造化プログラム定理（structured program theorem） あるいは ベーム-ヤコピーニの定理（Böhm-Jacopini theorem）とも呼ばれる定理は, の結論である。この定理は、もしも3つだけの手段（制御構造）で手続きを構築するならば、制御フローグラフの一分類（歴史的にフローチャートと呼ばれる）があらゆる計算可能関数を表現できることを述べている。
3つだけの手段（制御構造）は、以下のものである。
しかしながら、これらの制約に従う構造化チャートは、プログラムがテープの位置によって表現される情報を追跡するためにビット形式の追加変数（整数の変数）を使うかもしれない。この構造はベーム（Böhm）のプログラミング言語 P′′ (P double prime) に基づいている。
この理論はコラド・ベーム（Corrado Böhm）とジュゼッペ・ヤコピーニ（Giuseppe Jacopini）による1966年の論文に功績があると一般的に思われている。デイヴィッド・ハレル（David Harel）は、ベーム-ヤコピーニの論文が特に構造化プログラミングの支持者とともに「万人向けの評判」を享受したと1980年に書いた。ハレルは「その論文の技巧的様式が原因で「1966年のベーム-ヤコピーニの論文」は詳細に読まれるよりも明らかにより頻繁に引用されている」とも言及した。そして、1980年までに出版された大量の論文を再調査した後、ハレルはベーム-ヤコピーニの証明の内容は民間伝承的定理（folk theorem）として常に誤って伝えられてきたと主張した。民間伝承的定理は本質的に単純化された結論を含んでおり、ジョン・フォン・ノイマン（John von Neumann）とクリーネ（Kleene）の論文の近代的コンピューター理論の初期にさかのぼることができる。
ハレルは、より一般的な名前は1970年代初頭に構造化定理（The Structure Theorem）としてIBMの研究員によって提案されたとも書いている。
このバージョンの定理は、元のプログラムの制御フローの全てを単一のグローバルな codice_1 ループに置き換える。このループはプログラムカウンターを模しており、元の非構造化プログラムにおける全てのラベル（フォローチャートの箱型の図形）に行くことができる。ハレルはコンピューターの初期に痕跡を残す2つの論文にこの民間伝承的定理の起源を突き止めた。1つは1946年のノイマン型の説明であり、1つのwhileループを使ってどのようにプログラムカウンターを制御するのかということを説明している。ハレルは、構造化定理の民間伝承バージョンによって使われる単一のループは基本的にノイマン型コンピューターにおけるフローチャートの実行のための操作的意味論を提供しているだけであると言及している。もう一つは、ハレルがこの定理の民間伝承バージョンを追跡して見つけたより古い出典であり、1936年からのスティーヴン・コール・クリーネのである。
ドナルド・クヌースは、元のプログラムの構造がこの変換によって完全に失われていることを指摘することによってこの形式を批判した。この形式は以下のような擬似コードになるだけである。同様にブルース・イアン・ミルズはこの手法について「ブロック構造の精神はスタイルであり言語ではない。ノイマン型コンピューターを模することによって、ブロック構造言語の制限の範囲内であらゆるスパゲッティーコードの動きを作ることができる。このことはスパゲッティコードになることを防いでいない。」
ベームとヤコピーニの論文の証明は、フローチャートの構造的帰納法によって行う。それはを利用したので、ベームとヤコピーニの証明はプログラム変換アルゴリズムとして実用的ではなかった。そして、このような方向へのさらなる調査のためのドアを開けたのであった。
ベーム-ヤコピーニの証明は、プログラムを改良するよりもプログラムを不明瞭にする可能性が高かったので、ソフトウェア開発のために構造化プログラミングを採用するかどうかという疑問を解決しなかった。
それどころか議論の始まりを告げることになった。エドガー・ダイクストラの有名な文書「（Go to 文は有害と考えられる）」は1968年にその議論に続いた。
幾人かの研究者はベーム-ヤコピーニの結論に対して純粋な手段を取った。そして、ループの途中にある codice_2 と codice_3 ですらベーム-ヤコピーニの証明に必要とされていないので悪い実践であると主張した。したがって全てのループは単一の脱出ポイントを持つべきだと主張した。この純粋な手段はPascalプログラミング言語（1968～1969に設計）で具体化された。Pascalは1990年代中頃まで大学の入門的なプログラミングの講義をするために好まれたツールであった。
エドワード・ヨードンは、構造化プログラミングの流行が始まった時からの議論に基づいて、1970年代に非構造化プログラムを機械的に構造化プログラムに変換することに哲学的な反対があったと述べている。実用本位の対照的なこととして、そのような変換が既存のプログラムの大きなコードに役立ったということもあった。機械的変換のための最初の提案の一つは、エドワード・アッシュクロフト（Edward Ashcroft）と（Zohar Manna）による1971年の論文であった。
ベーム-ヤコピーニの定理の直接的応用は、構造化チャートに導入されている余分なローカル変数（訳注：ループ途中脱出用のフラグのことだろうか？）といくつかの重複コードという結果になったのかもしれない。後者の問題は、この状況で と呼ばれている（訳注：なぜ後者の問題なのかは英語版に書かれていない）。Pascal はこれらの問題の両方に影響されており、（Eric S. Roberts）によって引用された経験的研究に従っている。学生プログラマーであるロバーツは、いくつかの単純な問題（配列の中から1つの要素を検索する機能も含む）のために Pascal で適切な解法を公式化することに困難を感じた。ロバーツによって引用されたヘンリー・シャピロ（Henry Shapiro）による1980年の研究は、Pascal が提供する制御構造だけを使うと、適切な解法を得られた課題は20%だけだった。一方、ループの途中に return を書くことを許せば、この問題のために不適切なコードを書く課題は存在しなかった。
1973年、（S. Rao Kosaraju）は、任意の深さで multi-level break （多重ループから複数階層を一気に脱出できる break）を使えるようにすれば、構造化プログラミングにおいて余分な変数の追加を回避できることを証明した。さらにコサラジュは「プログラムの厳密な階層が存在する。それは現在 "コサラジュ階層（Kosaraju hierarchy）" と呼ばれている。"n" はあらゆる整数である。深さ "n" の1つの multi-level break を含んでいるプログラムは、"n" よりも小さい深さの multi-level break を使ったプログラムとして書き換えることはできない」ということを証明した。コサラジュは BLISSプログラミング言語の multi-level break の仕組みを引き合いに出している。codice_4 という形式の multi-level break は、実際に BLISS-11 で導入されていた。最初の BLISS は single-level break （一階層しか脱出できない break）のみを採用していた。BLISS言語ファミリーは制約のない goto を提供していなかった。Javaプログラミング言語は、後に同様にこの手法を採用している。
コサラジュの論文から得られる単純な結論は、あるプログラムが2つの異なる脱出口を持つループを含んでいないときだけ（変数を追加せずに）あるプログラムを構造化プログラムへ変換できるということである。変換可能性はコサラジュによって定義された。大雑把に言うと、同一の機能を処理し、同じ「基本動作」を使い、そして元のプログラムと同様であると断言できることである。しかし、元のプログラムと異なる制御フロー構造を使うことができる（これはベーム-ヤコピーニの使ったものよりも狭い概念の変換可能性である）。この結論に触発されて、コサラジュが頻繁に引用する循環的複雑度の概念を導入した論文の第6節において、トーマス・J・マッケイブ（Thomas J. McCabe）は非構造化プログラムの制御フローグラフ（CFG : Control Flow Graph）のためのと類似したものを記述した。つまり、プログラムのCFGを非構造化にする最小の誘導部分グラフである。これらの部分グラフは自然言語で非常に良く説明できる。それらは以下のものである。
マッケイブはこれらの4つのグラフが部分グラフとして登場するときに独立していないことを実際に明らかにした。プログラムが非構造化になるための必要十分条件は、そのCFGがこれらの4つのグラフから3つ選んで作った部分集合のどれか1組を部分グラフとして持つことである（訳注：4つのグラフのうち3つのグラフがCFGに含まれていたら非構造化になるということ）。彼は、もしも非構造化プログラムがこれらの4つの部分グラフの1つを含んでいるならば、その非構造化プログラムは4つの部分グラフからもう1つの異なる部分グラフを含まなければならないということも明らかにした。この後者の結論は、非構造化プログラミングの制御フローが一般的にスパゲティプログラムと呼ばれるものにどのようにしてなっていくのかを説明するのに役立つ。マッケイブは、あるプログラムが与えられたとき、それが理想の構造化プログラムからどの程度かけ離れているのかを定量化する数値測定手段も考案した。マッケイブは彼の測定手段を と呼んだ。
マッケイブの構造化プログラミングにおけるの特徴づけは不完全であると考えることができる。少なくともダイクストラのD構造（訳注：D構造の意味不明）は、建設用ブロックと見なされている。
1990年まで既存プログラムのほとんどの構造を維持しながら goto を削除するためにかなり多くの提案された手法が存在した。この問題への様々な手段はいくつかの等価の概念も提案した。それらの概念は上で議論された民間伝承的定理のような結果を避けるために単純なよりも厳密である。選ばれた等価の概念の厳密性は必要とされる制御フローの最小セットを要求する。ライル・ラムショウ（Lyle Ramshaw）による1988年の の論文は、それまでのその分野を調査しており、さらに自身の手法も提案している。ラムショウのアルゴリズムは、Java仮想マシンコードがオフセットとして表現された対象を持つ分岐命令を持つので、Javaの逆コンパイラの例のために使われた。しかし、上位レベルのJava言語だけは multi-level の codice_2 と codice_6 文を持っている。
Ammarguellat (1992年)は、ループの一箇所からの脱出を強制するために後戻りする変換手法を提案した。
1980年代にIBMの研究員（Harlan Mills）は、COBOL Structuring Facility の開発を監督した。COBOL Structuring Facility はCOBOLコードへの構造化アルゴリズムを応用した。ミルズの変換は各手続に対して以下の手順を必要とした。この構造は選択文のいくつかの選択肢をサブルーチンにすることによって改善できることに注意すること。以上で扱われていない資料：