Иди и не иди! доказательство этого:

Question

это доказательство:

каждый алгоритм A , разработанный с использованием go to или чего-то подобного, эквивалентен другому алгоритму B , который не использует go.

другими словами:

каждый алгоритм, разработанный с использованием go, может быть разработан без использования go.

как доказать?

Answer 1

C. Бём, Дж. Якопини, "Блок-схемы, машины Тьюринга и языки только с двумя правилами формирования", Comm. ACM, 9 (5): 366-371, 1966.

http://en.wikipedia.org/wiki/Structured_program_theorem

http://en.wikipedia.org/wiki/P"

Доказательство Бёма-Якопини описывает, как построить структурированную блок-схему из произвольной диаграммы, используя биты в дополнительной целочисленной переменной, чтобы отслеживать информацию, которую исходная программа представляет в месте расположения программы. Эта конструкция была основана на языке программирования Бёма P ′ ′. Доказательство Бёма-Якопини не решило вопрос о том, следует ли использовать структурированное программирование для разработки программного обеспечения, отчасти потому, что конструкция скорее всего затеняет программу, чем улучшит ее. Напротив, это стало сигналом к ​​началу дебатов. В 1968 году последовало знаменитое письмо Эдсгера Дейкстры «Перейти к утверждению, которое считается вредным». Последующие доказательства теоремы касались практических недостатков доказательства Бёма-Якопини с конструкциями, которые поддерживали или улучшали ясность исходной программы. 1

Answer 2

Каждая компьютерная программа может быть выражена без ветвления. Вам понадобится бесконечно длинная программа, но это можно сделать. (Вам все еще нужно заявление if) Я думаю, что именно здесь вы получите официальное доказательство. http://www.jucs.org/jucs_2_11/conditional_branching_is_not/Rojas_R.html

Кроме того, любой блок кода, который вы могли бы GoTo, можно выделить и поместить либо в конечный автомат, либо в цикл повторения. Если вы возьмете блок кода, заполненный случайным образом (и перекрывающиеся операторы 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, где goto-point может быть переменной.