Sansism Turing-completeness proof

It can be shown that Sansism is Turing-complete by showing that every program written in Brainfuck (a known Turing-complete language) can be converted into a Sansism program exhibiting the same behaviour. This page outlines the conversion process - for a formal algorithm see the external resource 'Sansism Turing-Completeness Proof'.

The commands + - , and . behave in the same way in the two languages, so no change is necessary.

If MD (memory director) is pointing right, < and > can be converted into ! and ##!## (note that the second conversion maintains the direction of MD).

A loop of the form 'entry[code]exit' can be converted into a Sansism loop of the form:

     G    G  GG
     >codeG++-G
entryG       > exit

Note that the top line and right section can be moved away in order to create space for further inner loops.

External resources

• Sansism Turing-Completeness Proof (from the Wayback Machine; retrieved on 3 January 2010)