Turing Complete Programming On ARM With Two Instructions

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.

Adding some Brainfsck to your ARM, inside your GBA.
Adding some Brainf**k to your ARM, inside your GBA.

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.

Tip kindly provided by [eeucalyptus].

14 thoughts on “Turing Complete Programming On ARM With Two Instructions

        1. There is no barrel shifter since Brainfuck can only increment and decrement numbers. Conditional execution is done by using self-modifying code to jump to one of two immediate addresses (the program counter is a general purpose register on ARM).

    1. I figure it was messing around with general purpose registers just from the title, so probably similar to same tricks known for years on Z80s.

      Implementing same thing with a couple of cheap doppler modules and the vibrational modes of a coffee can is left as an exercise to the reader.

    2. Basic addition and subtraction can be done by abusing writeback, data cells are represented as a linked list which can be traversed using only loads and stores, Brainfuck instructions must be converted into certain addresses by a script and inserted at the end of the ROM, and conditional execution is done with self-modifying code.

      For more detail, check out the blog post https://github.com/KellanClark/armfuck

  1. Back in the 1980s, a friend of my friend implemented a OIC (One Instruction Computer) at UMIST, implemented it out of logic, built a compiler for it, etc.

    The single instruction was (if I remember correctly) “reverse subtract, branch if borrow”.

Leave a Reply

Please be kind and respectful to help make the comments section excellent. (Comment Policy)

This site uses Akismet to reduce spam. Learn how your comment data is processed.