проверенный:
каждый алгоритм, как который разработанное использование переходит в или что-то, эквивалентность другому алгоритму B, который не использует, переходят в.
другими словами:
разработанное использование каждого алгоритма переходит в, может быть разработан без использования, переходят в.
как проверить?
С. Бем, Дж. Якопини, "Блок-схемы, машины Тьюринга и языки только с двумя правилами формирования", Comm. ACM, 9 (5): 366-371,1966.
http://en.wikipedia.org/wiki/Structured_program_theorem
http://en.wikipedia.org/wiki/P "
Доказательство Бёма-Якопини описывает, как построить структурированную блок-схему из произвольная диаграмма, использующая биты в дополнительной целочисленной переменной для отслеживания информации, которую исходная программа представляет посредством местоположения программы. Эта конструкция была основана на языке программирования Бема P ′ ′. Доказательство Бема-Якопини не решило вопрос о следует ли применять структурированное программирование для разработки программного обеспечения, отчасти потому, что конструкция скорее скрывала бы программу, чем улучшала ее. Напротив, это знаменовало начало дебатов. Знаменитое письмо Эдсгера Дейкстры «Перейти к утверждению, которое считается вредным», последовало в 1968 году. Последующие доказательства теоремы устраняли практические недостатки доказательства Бема-Якопини с конструкциями, которые поддерживали или улучшали ясность исходной программы. 1
Каждая компьютерная программа могла быть выражена без ветвлений. Вам понадобится бесконечно длинная программа, но это можно сделать. (Вам все равно понадобится оператор if) Я думаю, именно здесь вы получите свое формальное доказательство. http://www.jucs.org/jucs_2_11/conditional_branching_is_not/Rojas_R.html
Кроме того, любой блок кода, к которому вы можете перейти, можно выделить и поместить в конечный автомат, или повторение цикла. Если вы возьмете блок кода, заполненный случайными (и перекрывающимися операторами goto), то каждая точка перехода может быть назначена определенной функции, и каждый Goto может быть заменен на function_exit и присвоение следующего состояния.
Итак
Point1:
do something
Point2:
do something
if blah goto point3
goto point4
point3:
something
point4:
goto point2:
end
can be replaced by
function point1
do something
return = point2
end_function
function point2
do something
if blah return = point3
return = point4
end_function
function point3
something
return = point4
end_function
function point4
return = point2
end_function
state = point1
repeat
state = call_function (state)
until (state=end)
Это полностью эмулирует goto без использования goto, и поэтому я бы ответил - да.
Я не уверен, что goto может быть переменной.