Home Fetlang is turing complete
Post
Cancel

Fetlang is turing complete

Recently, the esoteric programming language Fetlang was linked and discussed on /r/programming. On the project’s GitHub page I noticed something in its list of features:

Probably Turing complete

is what 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 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 trough my process, which should also help you a lot if you ever decide you need to write erotica while at work. Note that this overview is entirely functional and ignores the many unique features of Fetlang which enables you make your code more prosaic, 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

1
2
3
4
5
6
7
8
9
10
11
12
13
( Parens make comments )

( Erik is a fraction variable. The following code assumes "standalone" lines, i.e. a previously uninitialized 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. Since Erik defaults to 0, he is licked once, hence Erik is 1)
Lick Erik forty five times ( Sets Erik to 45 )

( And if Erik is already set and needs to be reset )
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:

1
2
3
4
5
6
7
8
9
10
11
12
(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 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 a chain. It is, in essence, a “for-in” loop.

1
2
3
4
5
6
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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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 through 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:

1
2
3
4
5
6
7
8
9
10
11
12
13
( 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.

1
2
3
4
5
6
7
8
9
10
11
12
( 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:

1
2
3
4
5
6
7
8
9
10
11
12
13
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 figure out how to spell the numbers, 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 through the current state of the automaton (via bondage loop + iteration counter), doing this for all but the outermost positions:

1
2
3
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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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 figuring all this out. If you want to understand my proof in more detail, check out the code on Github or just ask.

The Fetlang repository no longer says that it is probably turing complete - they are sure now.

This post is licensed under CC BY 4.0 by the author.