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 its Turing completeness. Initially I wanted to do Conways Game of Life, always a fun project, but Fetlangs 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 trough 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

So far, so easy.

Control Flow

Comparisions

Comparing numbers is easy enough:

However, there is no direct way to compare chains, and figuring out a 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.

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:

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:

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.

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:

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:

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:

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:

 

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

The result of my hand-written code

The result of my hand-written code

It get's more repetitive if you zoom out.

A much larger generated Rule 110 picture, with only the rightmost bit set to 1

I wonder what an actual program in Rule 110 looks like

A much larger generated Rule 110 picture, with bits set semi-randomly

Thank you for reading !

 

 

 

Leave a Reply

Your email address will not be published. Required fields are marked *

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