Maze

Maze is a programming language based on variables that move over instructions. Each Variable is called a Car. Their passage is guided by walls and other controls.
==Syntax==
===Maze controls===
Symbol 	Description
## 	Wall. Cars will not pass through these.
.. 	Path. Cars will follow these.
, 	Separator. Put this after every command (except at end of line.)
<> 	Splitter. Create a new thread.
42 	Any two-digit numeral. Pause the car for this amount of 'ticks'.
^^ 	Start. One per maze only.
() 	Hole. Kill cars.
>> 	Print. Output the value held by the car.
<< 	Grab. Input a value.
Will turn into a wall after being run over.	
%L, %R, %D, %U 	Directions. Force the car to go Left, Right, Down or Up.
** 	Signal. See below.
AA 	Any two letters. A function to be applied to the car.
===Function commands===
Command 	Description
= 	Make equal to. Assign a new value to the car.
Subtracts a value from the car and store the result in the car.	
Addition. Similar to -= 	
*= 	Multiplication. Similar to -=
/= 	Division. Similar to -=
<=, ==, >=, >, < 	Comparative statements.
%L, %R, %D, %U 	Directions. Force the car to go Left, Right, Down or Up.
** 	Signal statement. Return true if there exists a signal in the maze that has a car on it, false otherwise.
IF conditionTHEN statementELSE statement 	Conditional branch statement.
// 	Comment. Ignore the rest of the line.
Define. Assign a function to a function name. 	
Functions are defined by putting 2 letters in the maze in the path of the car. The code for the function follows the maze.
Example:
 AA-> ="Hello" //Make car equal Hello
 AB-> IF ** THEN %U ELSE %D //If there is a signal in the maze with a car on it, the car will go UP. If not, it will go down.
 AC-> -=30 //Subtract 30 from value of car
Timing:
Every 'Tick', every car will move 1 step.
==Examples==
===Hello World===
 ##,##,##
 ##,^^,## //Car Starts
 ##,AA,## //Do AA to Car
 ##,>>,## //Print Car
 ##,(),## //Destroy Car
 ##,##,##
 
 AA-> ="Hello World!"
===99 bottles of beer===
 ##,##,##,##,##,##,##,##,##,##,##,##,##
 ##,##,##,##,##,^^,##,##,##,##,##,##,## //Start Car
 ##,##,##,##,..,<>,..,..,##,##,##,##,## //Make New Car
 ##,..,..,..,..,##,##,..,##,##,##,##,##
 ##,..,##,##,##,..,..,<>,..,..,##,##,## //Make New Car
 ##,AA,##,##,##,AB,##,##,##,AC,##,##,## //Set Values of Cars
 ##,%D,..,..,##,%D,..,..,##,%D,..,..,## //Make sure car goes down
 ##,>>,##,..,##,..,##,..,##,..,##,..,## //Printing...
 ##,..,##,>>,##,>>,##,>>,##,..,##,AC,##
 ##,>>,##,..,##,..,##,..,##,..,##,>>,##
 ##,..,##,..,##,..,##,..,##,>>,##,AF,##
 ##,AD,**,AG,##,..,AE,..,##,..,AE,..,## //Have we got to one?
 ##,(),##,##,##,##,(),##,##,##,(),##,## //Destroy Cars
 ##,##,##,##,##,##,##,##,##,##,##,##,##
 
 AA-> =99
 AB-> ="Bottles of Beer on the wall,"
 AC-> ="Bottles of Beer\n"
 AD-> IF == 1 THEN %D ELSE %R
 AE-> IF ** THEN %R ELSE %D
 AF-> ="You Take one down, Pass it around,"
 AG-> -= 1
===Truth-machine===
 ##,##,##,##,##,##,##
 ##,##,##,^^,##,##,##
 ##,##,##,<<,##,##,##
 ##,(),>>,AA,>>,..,##
 ##,##,##,..,##,..,##
 ##,##,##,..,..,..,##
 ##,##,##,##,##,##,##
 
 AA-> IF ==0 THEN %L ELSE %R
===Fibonacci sequence===
This program works in the Python interpreter below.
 ##,##,## // fibonacci
 ##,##,^^,##,##
 ##,..,<>,PP,##
 ##,..,##,..,##,##,##,##,##,##,##,## // left column is fib(n), right column is fib(n+1).
 ##,##,##,##,##,%D,..,LD,..,**,..,..,..,..,..,## // the small left loop sets fib(n) to 0; simultaneously,
 ##,..,..,..,##,>>,##,..,## ##,##,##,##,##,..,## // the small right loop sets a clone of fib(n+1) to fib(n+1)+f(n).
 ##,MM,##,..,##,..,##,..,##,##,..,..,..,##,..,## // (this technique is similar to brainfuck [->+<])
 ##,..,**,FL,..,02,##,%R,..,##,..,##,PP,##,..,## // the small loop at the bottom does nothing, but make sure
 ##,##,##,NL,##,##,##,%D,<>,01,FR,..,..,##,..,## // that the original fib(n+1) is synchronized with the other cars.
 ##,>>,##,##,##,..,##,##,03,##,##,##,..,## // then fib(n+1) goes to left column and fib(n+1)+fib(n) to right column
 ##,(),##,..,..,FM,..,..,%R,..,..,..,..,##
 ##,##,##,..,##,..,##,##,##,##,##,##,##,##
 ##,..,..,..,##
 ##,##,##,##,##
 PP-> +=1
 MM-> -=1
 FR-> IF ** THEN %U ELSE %D
 FL-> IF ==0 THEN %D ELSE %L
 FM-> IF ** THEN %L ELSE %R
 LD-> IF ** THEN %L ELSE %D
 NL-> ="\n"
==Computational class==
Let's show that Maze is Turing complete, via reduction from 3-cell brainfuck +-><[], which is known to be Turing complete.
(See Collatz function for a proof that 3-cell brainfuck is Turing complete.)
Any 3-cell brainfuck program is equivalent to the following Maze program:
* Begin the Maze program with the code:
 ##,##,##,##,##,##,##
 ##,##,^^,##,##,##,##
 ##,..,<>,%R,..,##,##
 ##,02,##,%D,<>,..,##
 ##,..,##,..,##,..,##
* Translate brainfuck instructions into Maze, one instruction per line, as follow:
 ##,..,##,..,##,PP,## // +
 
 ##,..,##,..,##,MM,## // -
 
 ##,%D,..,%L,##,..,## // >
 ##,**,##,%D,..,..,##
 ##,..,##,..,##,##,##
 ##,SW,01,SW,..,..,##
 ##,..,##,**,##,..,##
 ##,03,##,03,##,..,##
 
 ##,..,##,%R,..,%D,## // <
 ##,..,..,%D,##,**,##
 ##,##,##,..,##,..,##
 ##,..,..,WS,01,WS,##
 ##,..,##,**,##,..,##
 ##,..,##,03,##,03,##
 
 ##,##,##,##,##,##,##,##,..,##,..,##,..,## // [
 ##,..,..,..,..,..,..,..,SW,..,SW,..,%D,##
 ##,..,##,##,##,##,##,##,..,##,..,##,..,##
 ##,..,##,..,..,..,..,..,SW,..,%D,##,..,##
 ##,..,##,..,##,##,##,##,..,##,..,##,..,##
 ##,..,##,..,##,..,..,..,%D,##,..,##,..,##
 ##,..,##,..,##,**,##,##,..,##,..,##,..,##
 ##,..,##,..,##,..,##,##,..,##,..,##,..,##
 ##,..,##,..,##,**,##,##,..,##,..,##,..,##,##,##,##,##,##,##,##
 ##,..,##,..,##,..,##,##,..,##,..,##,LO,..,**,..,**,..,**,..,##
 ##,..,##,..,##,**,##,##,..,##,..,##,..,##,##,##,##,##,##,**,##
 ##,..,##,08,##,16,##,##,..,##,SW,..,SW,..,..,..,..,..,##,..,##
 ##,..,##,..,##,..,##,##,..,##,..,##,..,##,##,##,##,..,##,..,##
 ##,..,##,..,##,..,##,##,SW,..,SW,..,SW,..,..,..,##,..,##,..,##
 ##,..,##,..,##,..,##,##,..,##,..,##,..,##,##,..,##,..,##,..,##
 
 ##,..,##,08,##,16,##,##,..,##,..,##,..,##,##,..,##,..,##,..,## // ]
 ##,..,##,..,##,..,..,..,..,##,..,##,..,##,##,..,##,..,##,..,##
 ##,..,##,..,##,##,##,##,##,##,..,##,..,##,##,..,##,..,##,..,##
 ##,..,##,..,..,..,..,..,..,..,..,##,..,##,##,..,##,..,##,..,##
 ##,..,##,##,##,##,##,##,##,##,##,##,..,##,##,..,##,..,##,..,##
 ##,..,..,..,..,..,..,..,..,..,..,..,..,##,##,..,##,..,##,..,##
 ##,##,##,##,##,##,##,##,##,##,##,##,##,##,##,..,##,..,##,..,##
 ##,..,..,..,..,..,..,..,..,##,..,##,..,##
 ##,..,##,##,##,##,##,##,##,##,..,##,..,##
 ##,..,##,..,..,..,..,..,..,..,..,##,..,##
 ##,..,##,..,##,##,##,##,##,##,##,##,..,##
 ##,..,##,..,##,..,..,..,..,..,..,..,..,##
 ##,..,##,..,##,..,##,##,##,##,##,##,##,##
* Append to the end of the program the code:
 ##,(),##,(),##,(),##
 ##,##,##,##,##,##,##
 
 PP-> +=1
 MM-> -=1
 SW-> IF ** THEN %R ELSE %D
 WS-> IF ** THEN %L ELSE %D
 LO-> IF ==0 THEN %R ELSE %D
How it works:When the program begins, three cars are created, each representing a brainfuck cell. The cars travel on three parallel routes; the car in the rightmost route is the "current" cell. Instructions + and - increment and decrement that car's value. Instructions > and < make the cars swap routes: the car matching the "new current cell" comes to the rightmost route and the other two follow accordingly. Instruction [ spawn three new routes, leading to the matching ]. Nested loops are not an issue, as long as extra routes from outer loops are moved to the right to get round inner routes. Similarly, ] spawn three routes that lead back to the matching [. Needless to say, all those peripheral routes must be continued in the body of the loop, parallel to the three main routes.
==External resources==
*A C++ Maze interpreter
*A Python Maze interpreter
Category:Languages
Category:two-dimensional languages
Category:Concurrent programming
Category:Turing complete
Category:Implemented
Category:Unknown year