"Tìm tất cả mã trong một nhị phân đã cho tương đương với sự cố dừng". Có thật không?

Question

Được chỉ đọc the highly voted question regarding Emulators và báo cáo kết quả

Nó được chứng minh rằng việc tìm kiếm tất cả các mã trong một nhị phân cho là tương đương cho vấn đề Tạm dừng.

Thực sự gặp khó khăn với tôi.

Chắc chắn điều đó không đúng? Nó không chỉ là một đồ thị phụ thuộc lớn?

Sẽ thực sự biết ơn vì một số thông tin chi tiết hơn nữa trong tuyên bố này.

Answer 1

Tôi tin rằng ý nghĩa của việc "tìm tất cả mã được thực thi", tức là tìm kiếm mức độ phù hợp, có thể kết hợp với mã được tạo động. Điều đó thực sự có thể được giảm đến vấn đề dừng.

Giả sử bạn có một công cụ phủ sóng hoàn hảo sẽ tìm mọi đoạn mã trong một chương trình có thể được thực hiện (vì vậy phần còn lại là mã chết). Với một chương trình P, công cụ này cũng sẽ có thể quyết định xem chương trình mở rộng (P ; halt) có bao giờ thực hiện lệnh halt hay không hoặc liệu phần halt có phải là mã chết hay không. Vì vậy, nó sẽ giải quyết vấn đề dừng lại, mà chúng ta biết là không thể giải quyết được.

Answer 2

Tôi không đồng ý với người lùn.

Sự cố tạm dừng nói rằng không có chương trình P tồn tại có thể mất bất kỳ chương trình nào và quyết định xem chương trình đó có thực hiện lệnh halt hay không. Hãy để tôi trích dẫn wikipedia:

Alan Turing đã chứng minh năm 1936 rằng thuật toán chung để giải quyết vấn đề dừng cho tất cả các cặp chương trình có thể không tồn tại. Chúng tôi nói rằng vấn đề tạm dừng là không thể giải quyết được trên các máy Turing.

Mặt khác chúng ta không cố gắng để làm như vậy chương trình/thuật toán, nhưng chúng tôi đang cố gắng tìm tất cả các mã trong này/những chương trình cụ thể (s). Nếu chúng ta đảo ngược kỹ sư chương trình và thấy rằng nó ngay lập tức gọi exit() (tình huống ví dụ rất lạc quan), chúng tôi đã chứng minh rằng nó sẽ gọi halt, trong khi nó là không thể ?!

Nếu chúng tôi đang cố gắng xây dựng trình mô phỏng có thể chạy bất kỳ chương trình nào chúng tôi sẽ không thành công kể từ đó bạn có thể (dễ dàng) giảm bớt vấn đề này với Halting. Nhưng thông thường bạn đang xây dựng một trình giả lập cho một cái gì đó giống như một Game Boy hỗ trợ một số lượng hữu hạn của hộp mực trò chơi (chương trình) và do đó nó có thể.

Answer 3

Sự cố tạm dừng cho các máy trạng thái hữu hạn có thể giải quyết được (mặc dù có thể mất nhiều kiếp ..... của vũ trụ) và bất kỳ máy nào bạn có thể mô phỏng là một máy trạng thái hữu hạn. Chỉ cần chạy chương trình, và số lượng các bước được giới hạn bởi số trạng thái có thể; nếu con số đó bị vượt quá mà không dừng lại thì chương trình sẽ không bao giờ dừng lại, vì nó phải nằm trong vòng lặp.

Thực tế, việc tìm kiếm tất cả mã là một vấn đề dễ dàng hơn nhiều trừ khi mã có thể sử dụng các hình ảnh được tính toán. Thay vì chạy mã, bạn chỉ cần lấy tất cả các nhánh chính xác một lần tại mỗi điểm nhánh có thể.

Answer 4

Tôi đồng ý với Larsman và tôi tin rằng đối số có thể được thực hiện chính xác. Đầu tiên, tôi phải đồng ý rằng "tìm tất cả các mã trong một nhị phân nhất định" có nghĩa là, trong một ngữ cảnh này, có một hàm tính toán duy nhất xác định byte nào trong một tệp nhị phân đầu vào tương ứng với các lệnh được thực thi.

CHỈNH SỬA: Nếu có ai không rõ ràng về lý do tại sao có sự cố ở đây, hãy suy nghĩ về mã máy bị xáo trộn. Việc tháo gỡ mã như vậy là một vấn đề không tầm thường. Nếu bạn bắt đầu tháo gỡ ở giữa một lệnh đa byte, bạn sẽ có được sự tháo gỡ sai. Điều này không chỉ phá vỡ các chỉ dẫn trong câu hỏi, nhưng thường là một vài hướng dẫn ngoài đó. vv nhìn vào nó. (ví dụ: google "obfuscation and disassembly").

Phác thảo chiến lược để làm cho điều này chính xác:

Đầu tiên, xác định một/mô hình máy máy tính lý thuyết, trong đó một chương trình được mã hóa trong hướng dẫn nhị phân đa-bit, giống như mã máy trên các máy tính "thực", nhưng làm chính xác (và như vậy mà nó là turing hoàn thành). Giả sử rằng mã nhị phân mã hóa chương trình và tất cả đầu vào. Điều này tất cả phải được thực hiện chính xác, nhưng giả sử rằng ngôn ngữ có một lệnh băm (mã hóa nhị phân) và một chương trình sẽ dừng nếu và chỉ khi nó thực thi lệnh 'tạm dừng'.

Trước tiên, hãy giả sử rằng máy không thể thay đổi mã chương trình, nhưng có bộ nhớ để hoạt động. (giả định vô hạn trong các trường hợp thú vị).

Sau đó, bất kỳ bit đã cho nào sẽ là lúc bắt đầu một lệnh chạy trong khi thực hiện chương trình, nếu không sẽ không chạy được. (ví dụ: nó có thể nằm ở giữa lệnh, hoặc trong dữ liệu hoặc "mã rác" - tức là mã sẽ không bao giờ chạy. Lưu ý rằng tôi đã không xác nhận những điều này là loại trừ lẫn nhau, ví dụ như lệnh nhảy có thể có một mục tiêu ở giữa một lệnh cụ thể, do đó tạo ra một hướng dẫn khác, "trên lần đầu tiên vượt qua" không giống như một lệnh thực hiện.).

Xác định ins (i, j) là hàm trả về 1 nếu nhị phân i có lệnh bắt đầu tại vị trí bit j, thực thi trong một chương trình được mã hóa bởi i. Xác định ins (i, j) bằng 0 nếu không. giả sử ins (i, j) được tính toán.

Hãy halt_candidate (i) là chương trình sau đây:

for j = 1 to length(i) 
    if(i(j..j+len('halt')-1) == 'halt') 
    if(ins(i,j) == 1) 
     return 1 
return 0 

Vì chúng ta không cho phép tự thay đổi mã trên, họ chỉ đường cho một chương trình để ngăn chặn là cho có được một 'dừng lại' hướng dẫn tại một số vị trí j được thực hiện. Theo thiết kế, halt_candidate (i) tính hàm dừng.

Điều này cung cấp một bản phác thảo rất thô sơ về một hướng của bằng chứng. tức là nếu chúng ta giả định rằng chúng ta có thể kiểm tra xem chương trình i có một lệnh tại vị trí j cho tất cả j, thì chúng ta có thể mã hóa hàm dừng.

Đối với một hướng khác, người ta phải mã hóa bộ mô phỏng của máy chính thức, bên trong máy chính thức. Sau đó, tạo một chương trình cộng với các đầu vào i và j để mô phỏng chương trình i và khi một lệnh tại vị trí bit j được thực hiện, nó trả về 1 và dừng. Khi bất kỳ lệnh nào khác được thực hiện, nó vẫn tiếp tục chạy, và nếu mô phỏng bao giờ mô phỏng một hàm 'tạm dừng' trong i, trình giả lập nhảy vào một vòng lặp vô hạn. Sau đó ins (i, j) tương đương với tạm dừng (giả lập (i, j)), và do đó vấn đề dừng lại ngụ ý vấn đề tìm mã.

Tất nhiên người ta phải giả định một máy tính lý thuyết cho điều này tương đương với vấn đề dừng nổi tiếng không thể giải quyết được. Nếu không, đối với một máy tính "thực", vấn đề dừng lại có thể giải quyết được nhưng có thể thu vào.

Đối với hệ thống cho phép tự sửa đổi mã, đối số phức tạp hơn, nhưng tôi mong rằng điều đó không khác.

CHỈNH SỬA: Tôi tin rằng bằng chứng trong trường hợp tự sửa đổi sẽ là triển khai trình giả lập mã cộng-tự-sửa đổi trong mã tĩnh cộng với hệ thống dữ liệu ở trên. Sau đó dừng lại với mã tự sửa đổi được cho phép cho chương trình i với dữ liệu x, cũng giống như tạm dừng trong mã tĩnh cộng với hệ thống dữ liệu ở trên với nhị phân chứa trình giả lập, i và x làm mã cộng với dữ liệu.