가기로 이동하지 마십시오! 이 증명 :

Question

이 카드 키입니다 :

모든 알고리즘 로 이동하거나 뭔가 같은 이동 사용하지 않는 다른 알고리즘 B에 등가이다 사용하여 설계된. 즉

:

로 이동을 사용하여 설계 모든 알고리즘은 이동 사용하지 않고 설계 할 수있다.

증명 방법?

Answer 1

C. Böhm, G. Jacopini, "흐름도, 튜링 기계 및 2 가지 형성 규칙 만있는 언어", 통신. ACM, 9 (5) : 366-371, 1966.

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

뵘-Jacopini 증명은 원래의 프로그램이 나타내는 정보를 추적하기 위해 별도의 정수 변수의 비트를 이용하여 임의의 차트에서 구조화 된 플로우 차트를 구성하는 방법을 설명

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

프로그램 위치별로 이 구조는 Böhm의 프로그래밍 언어 P "를 기반으로합니다. Böhm-Jacopini의 증명은 소프트웨어 개발을 위해 구조화 된 프로그래밍을 채택할지 여부에 대한 문제를 해결하지 못했습니다. 부분적으로는 프로그램을 개선하는 것보다 프로그램을 모호하게 만들 가능성이 높기 때문입니다. 반대로, 그것은 논쟁의 시작을 알렸다. Edsger Dijkstra의 유명한 편지 인 "Go To To Statement는 유해하다고 생각합니다."는 1968 년에 이어졌습니다.이 정리의 후속 증거는 Böhm-Jacopini 증명의 실용적인 단점을 원래 프로그램의 명확성을 유지하거나 향상시킨 구조로 해결했습니다. 1

Answer 2

모든 컴퓨터 프로그램은 분기없이 표현 될 수 있습니다. 무한히 긴 프로그램이 필요 하겠지만 할 수 있습니다. (당신은 여전히 ​​if 진술이 필요합니다) 그것이 당신이 당신의 공식적인 증거를 얻는 곳이라고 생각합니다. http://www.jucs.org/jucs_2_11/conditional_branching_is_not/Rojas_R.html

또한 GoTo가 될 수있는 모든 코드 블록을 분리하여 상태 시스템 또는 반복 루프에 배치 할 수 있습니다. 무작위 (그리고 중복 된 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-point가 변수가 될 수있는 goto에 대해 확실하지 않습니다.