Airline Food Turing-completeness Proof

← Back to Airline Food

To show that Airline Food is Turing-complete, we show that it is possible to simulate any Turing machine with an Airline food program. To do this, we use F. J. Faase's method, meaning we will first formalize how to write many small programs in Airline Food, which will serve as the building blocks for building Turing machines in Airline Food.

Moving, Copying, and Adding

We assume that we have a program to(x), which will move the pointer to the variable x. It will be Let's talk about x. if the variable is named, and it will be a series of Um,'s or Yeah,'s if it is unnamed. We also assume that we begin each program with the following:

What's the deal with 0?  Not like 0.
You ever notice 1?

First, we write the program zero(a), which sets the value of a positive variable a to 0:

zero(a)
to(a)
Just like 0.

Next, we write the program move(a,b), which adds the value in the variable a to the variable b, setting the variable a to 0. First, we create the following programs to make things more readable.

inc(a)
to(a)
It's kinda like 1.

dec(a)
to(a)
Not like 1.

for(a)
to(a)
So...

next(a)
dec(a)
Moving on...

while(a)
for(a)

endwhile(a)
to(a)
Moving on...

And then move(a,b) is simply:

move(a,b)
for(a)
    inc(b)
next(a)

If/Else, Logic

Assuming that 0 represents false and positive numbers represent true, we can form if statements with the following programs:

if(a)
to(a)
So...

endif(a)
zero(a)
Moving on...

And we can do ifelse statements with the following programs, using some temporary variable t:

ifelse(a,t)
zero(t)
inc(t)
if(a)
    dec(t)

else(a,t)
endif(a)
if(t)

endelse(t)
endif(t)

We can write an or(a,b,d) program that will put 1 in destination d if and only if either a or b is not 0:

or(a,b,d)
zero(d)
move(a,d)
move(b,d)

We can write an and(a,b,d) program that will put 1 in destination d if and only if both a and b are not 0:

and(a,b,d)
zero(d)
if(a)
    move(b,d)
endif(a)
zero(b)

And we can write a not(a,d) program that will put 1 in destination d if a is 0, and otherwise put 1:

not(a,d)
zero(d)
inc(d)
if(a)
    dec(d)
endif(a)

Comparing Values

We first define the following function, that when given two variables a and b, as well as three temporary variables t1, t2, and t3, will decrement a and b until one of them has reached 0, meaning it will subtract the minimum of a and b from both a and b:

subtractMinimum(a,b,t1,t2,t3)
for(a)
    copy(b,t1,t2)
    ifelse(t1,t2)
        dec(b)
    else(t1,t2)
        inc(t3)
    endelse(t2)
next(a)
move(t3,a)

Using this function, we are able to perform all sorts of comparisons:

notEqual(a,b,d,t1,t2)
subtractMinimum(a,b,t1,t2,d)
or(a,b,d)

Equal(a,b,d,t1,t2)
notEqual(a,b,t1,t2,d)
not(t1,d)

We can also recursively write functions to check if a number is equal to a particular value:

isZero(a,d)
not(a,d)

isOne(a,d)
if(a)
    dec(a)
    isZero(a,d)
endif(a)

isTwo(a,d)
if(a)
    dec(a)
    isOne(a,d)
endif(a)

Arrays

The final thing we must implement in order to make a Turing machine is a way of using arrays in Airline Food.

We specify an array be providing base, the first variable on the stack that is part of the array. This variable must be named base. Every variable on top of this variable in the stack is assumed to be in the array as well. We also provide i, a variable containing the index of the array (beginning with 0) that will be accesses, and a, the variable that will either have its value stored, or where the value that is retrieved from the array will be stored.

We begin with the following auxiliary procedure, that when given a, a variable containing a number, will generate 3 times the value of a unnamed variables (initialized to zero):

generate3(a)
for(a)
    What's the deal with airline food?
    Not like 1.
    What's the deal with airline food?
    Not like 1.
    What's the deal with airline food?
    Not like 1.
next(a)

The array is structured as follows: each value in the array is separated by 2 blank variables, which we are able to use to transfer information up and down the array. Given a variable a, we use the notation a+1 to mean the variable on top of a on the stack, a+2 to mean the variable on top of a+1, etc.

So our process for getting a variable from the array is as follows:

Generate 3 × i empty variables
Copy i to base and base+1
Let c denote the position of the pointer, set it to point at base+1
While the value in c is not 0:
1. Move the value in c to c+3
2. Move the pointer to (let c be) c+3
3. Decrement c
Copy the value in c+2 to c+1
Add the value in base to c
While the value in c is not 0:
1. Move the value in c+1 to c-2
2. Move the value in c to c-3
3. Move the pointer to (let c be) c-3
4. Decrement c
Replace the value in base with the value in base+2

In terms of actual code, it will look like this, where i is the index of the array, and d is the variable where we want the value to go. Once again, we let c denote the current location of the pointer:

getarray(i,d)
What's the deal with airline food?
copy(i,base,base+1)
inc(base)
generate3(base)
copy(i,base,base+1)
copy(i,base+1,base+2)
Let's talk about base.  Yeah,
So...
    move(c,c+3)
    Yeah, Yeah, Yeah,
    Not like 1.
Moving on...
copy(c+2,c+1,c)
It's kinda like base.
So...
    Yeah, move(c,c-3)
    Um, move(c,c-3)
    Um, Um, Um,
    Not like 1.
Moving on...
zero(base)
zero(d)
move(base+2,d)

The process for setting a value in the array is similar, although we only need to shift the value up the array, and not back down. The code for it will look as follows:

setarray(i,v)
What's the deal with airline food?
copy(i,base,base+1)
inc(base)
generate3(base)
copy(i,base+1,base)
copy(v,base+2,base)
Let's talk about base.  Yeah,
So...
    move(c,c+3)
    Yeah, move(c,c+3)
    Yeah, Yeah,
    Not like 1.
Moving on...
Yeah, Yeah, zero(c)
move(c-1,c)

It is worth noting that these will create far more variables than are strictly necessary for the array. Each time we want to access element $i$ of the array, we will create $3(i+1)$ new variables before doing so. This will ensure that every index in the array will exist before we attempt to get/set it, thus allowing the array to be used properly, but will potentially result in a lot of excess unused space.

It is also possible to write these programs without using generate3 and relying on the user to manager their own array memory, but for simplicity's sake, and since we are not concerned with time or space complexity to prove Turing-completeness, we will make our lives easier by assuming that Airline Food's arrays are correctly handled.

Turing Machine in Airline Food

Finally, we can prove the Turing-completeness of Airline Food.

Suppose we are given a Turing machine $M=(Q,\Sigma ,\Gamma ,\delta ,q_{0},0,q_{a},q_{r})$ , where $Q$ is the set of states, $\Sigma$ is the set of input symbols, $\Gamma$ is the set of tape symbols, $\delta :Q\times \Gamma \to Q\times \Gamma \times \{L,R\}$ is the transition function, $q_{0}\in Q$ is the initial state, $0\in \Gamma$ is the blank symbol, $q_{a}\in Q$ is the accepting state, and $q_{r}\in Q$ is the rejecting state. We assume that his Turing machine has a tape that is unbounded to the right and that its transition function is defined for every $(q,\gamma )\in Q\times \Gamma$ .

We use the function const(d, $n$ ) to mean that we put the value $n$ in variable d. In other words, it's zero(d) followed by It's kinda like 1. written $n$ times.

We say that the states of $Q$ are mapped to the numbers $0$ through $|Q|-1$ , where $q_{0}=0$ , $q_{a}=1$ , and $q_{r}=2$ . We say that the symbols of $\Gamma$ are mapped to the numbers $0$ through $|\Gamma |-1$ . We say that $L$ is mapped to $0$ and $R$ is mapped to $1$ . To simulate $M$ with input $w=(\sigma _{0},\sigma _{1},\dots ,\sigma _{n})$ in Airline Food code, we use the following algorithm:

Write the following:

What's the deal with 0?  Not like 0.
What's the deal with 1?
What's the deal with state?  zero(state)
What's the deal with head?  zero(head)
What's the deal with symbol?  zero(symbol)
What's the deal with newstate?  zero(newstate)
What's the deal with newhead?  zero(newhead)
What's the deal with newsymbol?  zero(newsymbol)
What's the deal with t1?  zero(t1)
What's the deal with t2?  zero(t2)
What's the deal with t3?  zero(t3)
What's the deal with t4?  zero(t4)
What's the deal with t5?  zero(t5)
What's the deal with base?  zero(base)

For

i

from

0

to

n

:

Write the following:

const(t1, $i$ )
const(t2, $\sigma _{i}$ )
setarray(t1,t2)

Write the following:

const(t2, $1$ )
while(t2)
    getarray(head,symbol)

For each

(q,\gamma )\in Q\times \Gamma

:

Let $(q',\gamma ',D)=\delta (q,\gamma )$

Write the following:

    zero(t1)
    copy(state,t1,t2)
    const(t2, $q$ )
    Equal(t1,t2,t3,t4,t5)
    if(t3)
        copy(symbol,t1,t2)
        const(t2, $\gamma$ )
        Equal(t1,t2,t3,t4,t5)
        if(t3)
            const(newstate, $q'$ )
            const(newsymbol, $\gamma '$ )
            copy(head,newhead,t1)
            const(t1, $D$ )
            ifelse(t1,t2)
                inc(newhead)
            else(t1,t2)
                copy(newhead,t3,t4)
                if(t3)
                    dec(newhead)
                endif(t3)
            endelse(t2)
        endif(t3)
    endif(t3)

Write the following:

    setarray(head,newsymbol)
    zero(symbol)
    zero(newsymbol)
    zero(head)
    move(newhead,head)
    zero(state)
    move(newstate,state)
    zero(t4)
    zero(t5)
    copy(state,t5,t3)
    copy(state,t4,t3)
    isOne(t4,t1)
    isTwo(t5,t2)
    or(t1,t2,t3)
    not(t3,t2)
endwhile(t2)
isOne(state,t1)
ifelse(t1,t2)
    const(t3, $65$ )
    See?
else(t1,t2)
    const(t3, $82$ )
    See?
endelse(t2)

This code, when run, will simulate the Turing machine $M$ on the input $w$ . Using an (unbounded) Airline Food array to simulate the tape, which it initializes to contain $w$ , it will keep track of a variable head, which holds the index of the array that we are currently updating (i.e., the head position of our Turing machine). In each iteration, it will get the current symbol, stored in the variable symbol, by going to position head of the array, and then depending on the current symbol and current state, stored in the variable state, will update the Turing machine accordingly. It does this by putting the new state, symbol, and head position into the variables newstate, newsymbol, and newhead, then updating the head to be newhead, and updating the state to be newstate. It will continue doing so until state is either $1$ or $2$ , meaning that it has reached state $q_{a}$ or $q_{r}$ , respectively, at which point it will output A if the machine accepts or R if the machine rejects.

This is a simulation of a Turing machine. Since it is possible to simulate any Turing machine in Airline Food, it is Turing-complete.

Airline Food Turing-completeness Proof

Moving, Copying, and Adding

If/Else, Logic

Comparing Values

Arrays

Turing Machine in Airline Food

Navigation menu

Search