# Airline Food Turing-completeness Proof

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:

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

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.

to(a) It's kinda like 1.inc(a)to(a) Not like 1.dec(a)to(a) So...for(a)dec(a) Moving on...next(a)for(a)while(a)to(a) Moving on...endwhile(a)

And then `move(a,b)`

is simply:

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

### If/Else, Logic

Assuming that 0 represents false and positive numbers represent true, we can form `if`

statements with the following programs:

to(a) So...if(a)zero(a) Moving on...endif(a)

And we can do `ifelse`

statements with the following programs, using some temporary variable `t`

:

zero(t) inc(t) if(a) dec(t)ifelse(a,t)endif(a) if(t)else(a,t)endif(t)endelse(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:

zero(d) move(a,d) move(b,d)or(a,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:

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

And we can write a `not(a,d)`

program that will put 1 in destination `d`

if `a`

is 0, and otherwise put 1:

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

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

:

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

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

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

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

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

### 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):

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)generate3(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:- Move the value in
`c`

to`c+3`

- Move the pointer to (let
`c`

be)`c+3`

- Decrement
`c`

- Move the value in
- Copy the value in
`c+2`

to`c+1`

- Add the value in
`base`

to`c`

- While the value in
`c`

is not 0:- Move the value in
`c+1`

to`c-2`

- Move the value in
`c`

to`c-3`

- Move the pointer to (let
`c`

be)`c-3`

- Decrement
`c`

- Move the value in
- 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:

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)getarray(i,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:

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)setarray(i,v)

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 of the array, we will create 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 , where is the set of states, is the set of input symbols, is the set of tape symbols, is the transition function, is the initial state, is the blank symbol, is the accepting state, and 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 .

We use the function `const(d,)`

to mean that we put the value in variable `d`

. In other words, it's `zero(d)`

followed by `It's kinda like 1.`

written times.

We say that the states of are mapped to the numbers through , where , , and . We say that the symbols of are mapped to the numbers through . We say that is mapped to and is mapped to . To simulate with input 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 from to :
- Write the following:
const(t1,) const(t2,) setarray(t1,t2)

- Write the following:
- Write the following:
`const(t2,) while(t2) getarray(head,symbol)`

- For each :
- Let
- Write the following:
zero(t1) copy(state,t1,t2) const(t2,) Equal(t1,t2,t3,t4,t5) if(t3) copy(symbol,t1,t2) const(t2,) Equal(t1,t2,t3,t4,t5) if(t3) const(newstate,) const(newsymbol,) copy(head,newhead,t1) const(t1,) 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,) See? else(t1,t2) const(t3,) See? endelse(t2)

This code, when run, will simulate the Turing machine on the input . Using an (unbounded) Airline Food array to simulate the tape, which it initializes to contain , 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 or , meaning that it has reached state or , 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.