A functional guide to Fetlang and its Turing completeness.

A short time ago, the esoteric programming language Fetlang was linked and discussed on the /r/programming subreddit.  On the Github page I noticed something in its list of features:

• Probably Turing complete

It used to say. I decided to do something about that and try to prove that it is, in fact, Turing complete. Initially, I wanted to implement Conway’s Game of Life, always a fun project, but Fetlang’s dense and unwieldy syntax made me drop down to easy mode: Rule 110, a much simpler Turing complete cellular automaton. The whole project took me around five hours, most of which were spent trying to figure out how to handle the two only data types. I’ll run you through my process, which should also help you a lot if you ever decide you need to write some erotica while at work. Note that this overview is entirely functional and ignores the many possibilities to turn your code into better prose, such as possessives and pronouns.

Understanding Fetlang

Understanding the Data Types

Fetlang has but two data types: Fractions and Chains. Fractions are what they say: Rational, non-float numbers. If they happen to have an ASCII-value, they can be printed to screen. Chains are linked lists of fractions and can be initialized by string literals. Fractions cannot be initialized by normal integer literals – rather, you have to spell out the numbers. Types are not changeable after initialization.

Initializing, setting and resetting

The following code will show you how to initialize variables

( Parens make comments )

( Erik is initialized as a fraction variable )
Worship Erik ( Sets Erik to 0. Worship multiplies, by 1 if no second argument is given. Erik is not initialized, but from context, must be a fraction, set to 0 by default)
Lick Erik ( Sets Erik to 1. Lick adds, adding 1 if no second argument is given. )
Lick Erik forty five times ( Sets Erik to 46 )

( If a value needs to be set to zero... )
Have Erik spank Erik ( Resets Erik to 0, by spanking (subtracting) him from himself )

( Tiffany is a Chain Variable )
Make Tiffany moan ( Declares Tiffany to be an empty chain. Can also be used to reset, if already set )
Make Tiffany moan "Wow, that's nice" ( String literals work. Concatenating is not directly possible )

So far, so easy.

Control Flow

Comparisions

Comparing numbers is easy enough:

(Set Anna to 1 and Betty to 2)
Lick Anna
Lick Betty two times

( Anna > Betty )
If Anna is dominant towards Betty
( Anna == Betty )
If Anna is Betty
( Anna < Betty )
If Anna is submissive to Betty
( Anna != Betty )
If Anna is not Betty

However, there is no direct way to compare chains, and figuring out the correct way to do this was the hardest part for me.

The Bind Operator (“Bondage Loops”)

A bondage loop allows access to all values inside of a chain. It is, in essence, a “for-in” loop.

Make Anna moan "Array"

Bind Emma to Anna
    Make slave scream Emma 

( Prints "A", "r", "r", "a", "y" on individual lines )

The important and neat thing here is that Emma is not a chain of length 1, but a fraction! This enables us to do many useful things.

There are also while and until loops, which are the most self-explanatory things in this language.

Checking for a specific ASCII-value

This is one more tool we’re going to need to write somewhat understandable code. Let’s try some things:

Make Anna moan "A"
Lick Betty sixty five times

(Print "A" two times)
Make Slave scream Anna
Make Slave scream Betty

(So, let's try...)

x If Anna is "A" (Can't use string literals in comparison)
x If Anna is Betty (Incompatible types)
x If Anna is sixty five (Can't use number literals either, also wrong types)

(So, uhmm....)

Bind Emma to Anna
   (Anna is a string literal, but Emma is not - she is a fraction!)
   If Emma is Betty ( This works! )

Neat.

Iterating trough a chain and assigning conditional values

So, now we can put these tools together to go from an input string to a series of conditional reactions, based on individual characters:

( This program detects if a string contains two zeroes in a row )
Make Anna moan "11101010100"
Lick AsciiZero forty eight times
Worship ZeroesInARow
Lick limit two times

Bind Emma to Anna
    If Emma is AsciiZero
        Lick ZeroesInARow
        If ZeroesInARow is limit
           Make Slave Scream "00 detected!"
    Otherwise
        Have ZeroesInARow Spank ZeroesInARow

And with this, there is just one more construct to understand for my proof code to become obvious

Adding to a Chain

Adding to a Chain/String can be done with the ‘hogtie’-operator. Here, a fraction has to hogtie a chain, writing the byte on its end.

( Generates the String "abcd" and prints it )
Make Anna moan
Lick char ninety seven times ( Set to "a" )
Worship counter
Lick loopmax four times

While counter is submissive to loopmax
    Lick counter
    Have char hogtie Anna
    Lick char
 
Make slave scream Anna

And that’s it. We’ve now fully learned to juggle the data types and can begin writing the actual program – which is now fairly easy.

 

Understanding the Turing completeness proof

Disclaimer: I’m 99% sure my code can be simplified or improved. But I don’t care.

To understand the steps the program takes, it’s probably best to look at my python generator code, which I wrote after completing the first version of the proof to expand the size of the Rule 110 board. Steps are:

def main():
        generateIntro()             // Initialize required variables
        generateNumbers()           // Initialize all required numbers, since you can't use literals in control flow
                                    // In the python code, this is inefficient, since I was too lazy to spell the numbers programmatically, so I have many, many lines of licking
        beginLoop()                 // Literally just the while loop and condition
        resetTempVariables()        // Does what it says
        setEmptyPositions()         // That's also resetting, come to think of it                
        incrementLoopCounter()      // Again, obvious
        printCurrentState()         // You probably get the idea 
        getParentStrings()          
        getDescendants()
        writeNextGeneration()       // Print the next generation
        saveNextGeneration()        // Save the next generation as current via bondage loop

Okay, so everything I’ve commented is pretty much boring cruft – setting and resetting values, mostly. Let’s look at the other functions:

getParentStrings()

Here we loop trough the current state of the automaton (via bondage loop + iteration counter), doing this for all but the outermost positions:

If counter is submissive to number4
    If counter is dominant towards number0
        Have Emma hogtie position2

This just builds a 3-character-Chain for each position, by taking its upper left, upper middle and upper right neighbor and saving it.

getDescendants()

This function requires a lot more code. First, we explicitly write the values of left, middle and right:

Bind Emma to position2
    if counter is number0
        If Emma is AsciiZero
            Have AsciiZero lick left
        Otherwise
            Have AsciiOne lick left
    if counter is number1
        If Emma is AsciiZero
            Have AsciiZero lick middle
        Otherwise
            Have AsciiOne lick middle
    if counter is number2
        If Emma is AsciiZero
            Have AsciiZero lick right
        Otherwise
            Have AsciiOne lick right
    
    Lick counter

Left, middle, right and counter are of course reset before each position is calculated.

Now we have three accessible variables for the current generation. A short if-tree gives us the calculated value for the next one:

 

if left is AsciiOne
    if middle is AsciiOne
        if right is AsciiZero
            Have AsciiOne hogtie nextposition2
        otherwise
            have AsciiZero hogtie nextposition2
    if middle is AsciiZero
        if right is AsciiOne
            have AsciiOne hogtie nextposition2
        otherwise
            have AsciiZero hogtie nextposition2
if left is AsciiZero
    if middle is AsciiOne
        Have AsciiOne hogtie nextposition2
    otherwise
        if right is AsciiOne
            Have AsciiOne hogtie nextposition2
        otherwise
            have AsciiZero hogtie nextposition2

And this is the entire trick. Rule 110 is incredibly simple, and thus very nice for these proofs.

I really enjoyed figuringall this out. If you want to understand my proof in more detail, check out the code on my github or just ask.

Let me end this with some nice pictures

Thank you for reading !