Abstrakt. Böhm-Jacopini-teoremet (Böhm och Jacopini, 1966) är ett klassiskt resultat av programschemat. Den säger att alla deterministiska flödesdiagram program är likvärdiga med en tid program. Teoremet är vanligtvis formulerat på första ordningen tolkad eller första ordningen otolkad (schematic) nivå, eftersom konstruktionen kräver införandet av hjälpvariabler. Ashcroft och Manna (1972) och Kosaraju (1973) visade att detta är oundvikligt. Som observerats av ett antal författare, en något mer kraftfull strukturerad programmering konstruktion, nämligen loop program med flera nivåer avbrott, är tillräckligt för att representera alla deterministiska flödesscheman utan att införa hjälpvariabler. Kosaraju (1973) upprättade en strikt hierarki som bestämdes av det högsta tillåtna bodjupet. I detta dokument ger vi en rent propositionell redogörelse för dessa resultat. Vi omformulerar problemen på propositionsnivå i termer av automata på bevakade strängar, den automatiska-teoretiska motsvarigheten till Kleene algebra med tester. Medan de klassiska tillvägagångssätten inte skiljer mellan första ordningens och propositionsnivåernas abstraktion, finner vi att den rent propositionella formuleringen möjliggör en mer strömlinjeformad matematisk behandling, med algebraiska och topologiska begrepp som bisimulation och myntinduktion. Med hjälp av dessa verktyg kan vi ge mer matematiskt rigorösa formuleringar och enklare och mer avslöjande bevis.
Detta resultat har omformulerats och bevisats på förslagsnivå i Ref.
The Böhm–Jacopini Theorem is False, Propositionally
{'venue': 'MPC', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}