Sansism Turing-completeness proof

From Esolang
Jump to navigation Jump to search

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
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