ĐI ĐẾN VÀ ĐỪNG ĐẾN! bằng chứng về điều này:

Question

là này khả năng chống:

mỗi thuật toán Một thiết kế sử dụng đến hoặc một cái gì đó như thế, là tương đương với thuật toán khác B mà không sử dụng đến.

nói cách khác:

mọi thuật toán được thiết kế sử dụng, có thể được thiết kế mà không cần sử dụng.

cách chứng minh?

Answer 1

C. Böhm, G. Jacopini, "Sơ đồ luồng, Máy móc và ngôn ngữ chỉ có hai quy tắc hình thành", Comm. của ACM, 9 (5): 366-371,1966.

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

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

Bằng chứng Böhm-Jacopini mô tả làm thế nào để xây dựng một biểu đồ dòng chảy có cấu trúc từ một biểu đồ tùy tiện, sử dụng các bit trong một biến số nguyên phụ để theo dõi các thông tin mà chương trình ban đầu đại diện bởi vị trí chương trình. Cấu trúc này dựa trên ngôn ngữ lập trình của Böhm P ′ ′. Bằng chứng Böhm-Jacopini không giải quyết được vấn đề liệu có áp dụng lập trình có cấu trúc cho phát triển phần mềm hay không, một phần vì việc xây dựng có nhiều khả năng che khuất một chương trình hơn là cải thiện nó. Ngược lại, nó báo hiệu sự khởi đầu của cuộc tranh luận. Bức thư nổi tiếng của Edsger Dijkstra, "Go To Statement Considered Harmful", tiếp theo năm 1968. Các bằng chứng tiếp theo của định lý đã giải quyết những thiếu sót thực tế của bằng chứng Böhm-Jacopini với các công trình duy trì hoặc cải thiện sự rõ ràng của chương trình gốc. 1

Answer 2

Mỗi chương trình máy tính đều có thể được biểu diễn mà không cần phân nhánh. Bạn sẽ cần một chương trình dài vô tận, nhưng nó có thể được thực hiện. (Bạn vẫn cần một câu lệnh if) Tôi đoán đó là nơi bạn sẽ nhận được bằng chứng chính thức của mình. http://www.jucs.org/jucs_2_11/conditional_branching_is_not/Rojas_R.html

Ngoài ra, bất kỳ khối mã nào bạn có thể GoTo, có thể được tách ra và đặt trong máy trạng thái hoặc lặp lại lặp lại. Nếu bạn lấy một khối mã đầy ngẫu nhiên (và các câu lệnh goto chồng chéo), thì mỗi điểm goto có thể được gán cho một hàm cụ thể, và mỗi Goto có thể được thay thế bằng hàm function_exit và gán cho trạng thái tiếp theo.

Vì vậy

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) 

này hoàn toàn mô phỏng goto mà không sử dụng goto, và vì điều này, tôi muốn trả lời - vâng.

Tôi không chắc chắn về goto nơi mà điểm goto có thể là một biến.