GO TO and DON'T GO TO ! proof of this:

Question

is this proofed:

every algorithm A designed using go to or something like, is equivalence to another algorithm B that does not use go to.

in other words:

every algorithm designed using go to, can be designed without using go to.

how to proof?

Answer 1

The proof is in all the languages that do not have a goto feature.

Answer 2

C. Böhm, G. Jacopini, "Flow diagrams, Turing Machines and Languages with only Two Formation Rules", Comm. of the ACM, 9(5): 366-371,1966.

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

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

The Böhm-Jacopini proof describes how to construct a structured flow chart from an arbitrary chart, using the bits in an extra integer variable to keep track of information that the original program represents by the program location. This construction was based on Böhm's programming language P′′. The Böhm-Jacopini proof did not settle the question of whether to adopt structured programming for software development, partly because the construction was more likely to obscure a program than to improve it. On the contrary, it signalled the beginning of the debate. Edsger Dijkstra's famous letter, "Go To Statement Considered Harmful," followed in 1968. Subsequent proofs of the theorem addressed practical shortcomings of the Böhm-Jacopini proof with constructions that maintained or improved the clarity of the original program.1

Answer 3

The goto feature can introduce "multiple entry loops", also known as "irreducible" loops. Elimination of irreducible loops is essentially achieved by duplicating code.

See Handling Irreducible Loops: Optimized Node Splitting vs. DJ-Graphs for a discussion of the ways in which this can be done.

Answer 4

Every computer program could be expressed without branching. You would need an infinitely long program, but it could be done. (You'd still need an if statement) I guess that's where you would get your formal proof. http://www.jucs.org/jucs_2_11/conditional_branching_is_not/Rojas_R.html

Also, any block of code you could GoTo, can be separated out and placed either in a state machine, or a Repeat Loop. If you take a block of code filled with random (and overlapping goto statements), then each goto point could be assigned to a specific function, and each Goto could be replaced with a function_exit and an assignation of the next state.

So

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)

This completely emulates goto without using goto, and because of this, I'd answer - yes.

I'm not sure about goto where the goto-point can be a variable.

Answer 5

The proof is: you can implement a universal Turing machine without goto's and you can implement any algorithm with a universal Turing machine and a character string representing its input.