Tôi đang tìm cách tạo một tập hợp con nhỏ, tính toán phổ quát của mã vạch x86 chữ và số. Cuối cùng, tôi muốn tập hợp con chứa ít hướng dẫn nhất có thể và nếu có nhiều tập con tối thiểu, tôi cũng muốn biết điều đó. Tập hợp con sẽ có thể mô phỏng bất kỳ chương trình nào có thể được viết bằng toàn bộ các chỉ lệnh chữ và số. Hướng dẫn chỉ nên bao gồm các hướng dẫn tương ứng với các ký tự "A-Z", "a-z" và "0-9".Turing Bộ chữ cái hoàn chỉnh chữ số x86 (tập hợp con)
Cho đến nay tôi nghĩ rằng một push, pop, inc, dec, cmp và je sẽ là đủ, nhưng tôi chắc chắn có một tập hợp nhỏ hơn. Làm thế nào tôi có thể đi về chứng minh rằng một bộ tôi tạo ra có thể mô phỏng bất kỳ chương trình bằng cách sử dụng tất cả các hướng dẫn chữ và số? Làm thế nào tôi có thể chứng minh rằng một bộ như vậy là tối thiểu? Có ai biết nếu một tập hợp chỉ dẫn như vậy tồn tại?
Bạn chắc chắn có thể xóa 'inc' hoặc' dec' khỏi danh sách, bạn không cần phải có cả hai. :) –
Không thể 'inc' và' dec' được thay thế bằng một chữ số-chấp nhận 'add'? – Nyerguds
Giống như Alexey đã nói, chỉ một trong 'inc' hoặc' dec' là cần thiết, bởi vì cuối cùng tràn sẽ xảy ra. – cytinus