Summary of TURING COMPLETE PROGRAMMING ON ARM WITH TWO INSTRUCTIONS
Kellan Clark implemented a Turing-complete computer and Brainf**k interpreter for ARM using only the LDM and STM 32-bit opcodes, demonstrating that powerful computation can arise from flexible data-movement instructions. Targeting processors like the ARM7TDMI (used in the Game Boy Advance), Armf**k shows how moving bytes between memory and 16 general-purpose registers suffices to implement BF programs and prove the concept.
Parts used in the Armf**k project:
- ARM processor with 32-bit ISA (e.g., ARM7TDMI)
- LDM opcode (Load Multiple)
- STM opcode (Store Multiple)
- 16 general-purpose registers (GPRs)
- Brainf**k language (as target esoteric language)
- Armf**k interpreter implementation by Kellan Clark
- Game Boy Advance (as an example target platform)
There are many questions that can be asked for software projects, with most of these questions starting with ‘Why…?’. This is true for the challenge of proving that cascading stylesheets are Turing-complete, or that you don’t need all those fancy ISA bits of an ARM processors when you already got the LDM and STM commands in the 32-bit ISA. What originally started off as a bit of a running gag in a group of developers led to [Kellan Clark] implementing a Turing-complete computer and a functioning interpreter using nothing but these two opcodes.
These two opcodes essentially allow the storing or reading of data into memory from any combination of the 16 general-purpose registers (GPRs). This makes them both extremely versatile and also extremely open to ‘abuse’ like in this example. For a straightforward implementation that could prove the concept, [Kellan] decided to pick one of everyone’s favorite esoteric programming languages: Brainf**k, creating the charmingly titled Armf**k that allows anyone to write BF programs for any suitable ARM processor, like the ARM7TDMI in the Game Boy Advance that [Kellan] targeted.
As a proof of concept it’s unquestioningly intriguing, and a great example of how the most powerful parts of any ISA are those that move data around. After all, as anyone who writes ASM and C knows, computers are just machines that can copy bytes around really fast to make stuff happen. Mind-blowing examples like these serve to illustrate that point quite well.
Source: TURING COMPLETE PROGRAMMING ON ARM WITH TWO INSTRUCTIONS
- What two opcodes are used to implement Armf**k?
The LDM (Load Multiple) and STM (Store Multiple) opcodes are used. - Can ARM be made Turing-complete with only two instructions?
Yes, the project demonstrates Turing-completeness using only LDM and STM. - What language was chosen for the proof of concept?
Brainf**k was chosen as the esoteric language for the proof of concept. - Which ARM registers are exploited in this approach?
The 16 general-purpose registers (GPRs) are used for storing and reading data. - What target platform did Kellan Clark use as an example?
The Game Boy Advance, using the ARM7TDMI, was targeted as an example platform. - Why are LDM and STM powerful enough for this proof?
Because they allow storing or reading data into memory from any combination of the 16 GPRs, enabling versatile data movement needed to implement computation. - Does the project include an interpreter implementation?
Yes, Kellan Clark implemented a functioning interpreter called Armf**k.
