The MOS 6502 is (Mostly) Turing-Complete Without Registers
owl writes:
http://oldvcr.blogspot.com/2023/01/the-mos-6502-is-mostly-turing-complete.html
It is known that the x86 MOV instruction is Turing-complete (PDF) all by itself, and is even a compiler target. More usefully, x86 can be made Turing-complete without the overt use of any registers.
These tricks work primarily because the ISA allows memory-to-memory operations, i.e., altering a memory location without explicitly moving data through a program-visible register, a historical holdover from its roots in the Intel 8086 and its ancestors. (Let's not even talk about its Turing-complete faults.) Other pre-RISC CPUs of that era also have memory-to-memory addressing, including the MOS 6502, which despite its simplicity being inspiration for the RISC ARM architecture is not itself RISC. It should be no surprise you can make the 6502 do this trick too even with its more constrained instruction set, and we can do it with just four instructions, not counting rts to return to the operating system.
Read more of this story at SoylentNews.