5
영숫자 x86 opcode의 최소한의 계산 상 범용 서브 세트를 만들려고합니다. 결국에는 하위 집합에 가능한 한 적은 수의 명령어가 포함되도록하고, 여러 개의 하위 집합이있는 경우이를 알고 싶습니다. 서브 세트는 전체 영숫자 명령어 세트로 작성 될 수있는 프로그램을 시뮬레이트 할 수 있어야합니다. 지침에는 "A-Z", "a-z"및 "0-9"문자에 해당하는 지침 만 포함해야합니다.Turing Complete 영숫자 x86 명령어 세트 (서브셋)
지금까지 나는 push, pop, inc는, dec, cmp 및 je 충분 것이라고 생각하지만, 나는 작은 세트가 확신합니다. 내가 생성하는 세트가 모든 영숫자 명령어를 사용하여 모든 프로그램을 시뮬레이션 할 수 있다는 것을 증명할 수있는 방법은 무엇입니까? 그러한 세트가 최소한이라는 것을 어떻게 증명할 수 있습니까? 그러한 명령어 하위 집합이 존재하는지 아는 사람 있습니까?
반드시 목록에서 'inc'또는 'dec'중 하나를 삭제할 수 있습니다. 둘 다 가질 필요는 없습니다. :) –
'inc'와 'dec'을 하나의 음수 - 수락 'add'로 대체 할 수 없습니까? – Nyerguds
알렉세이 (Alexey)가 말했듯이 결국에는 "inc"또는 "dec"중 하나만 필요합니다. 결국 오버플로가 발생하기 때문입니다. – cytinus