Dominik Muth firstname.lastname@example.org
make -B [MACHINE=your_machine.h] [TAPE=your_tape.h] [X=[0|1|2|3|4|5|6|7|8|9]] [V=[0|1|2]] run
make -B V=2 run strings prog | grep '(,)' make -B MACHINE=machine_times2.h TAPE=tape_five.h V=1 run make -B MACHINE=machine_chaos_5_2.h X=5 run
This is something we were fearing all along: that the C preprocessor is Turing-complete even without conditionals and recursive file inclusion as some kind of a rewriting system. Now we have the proof!
#ifs or other conditional directives, only
V=0(default) only prints the final tape
V=1additionally prints one tilde character per machine step (slow)
V=2additionally prints details on each machine step (slow; generates large files)
./progand filters a little statistics out of the verbose output
X(defaults to 3) sets the maximum number of steps: M(
X) ~ 8
If the machine does not halt after M(
X) steps, you will see unexpanded macros in the output.
V=2 is used, you may see “
warning: string length is greater than the length '4095' ISO C99 compilers are required to support”.
Implementing your own Turing machine is easy. Take a look at the supplied header files for examples.
Every symbol used (except “
_”) must be explicitly declared using
#define sym_SYMBOL(sym, _SYMBOL) sym
#define sym_1(sym, _1) sym
The initial content of the tape must be defined in the tape header using a triple like:
#define tape ((((,),...l2), l1), c, (r1, (r2..., (,))))
l2, … are the symbols to the left
cis the symbol at the current position
r2, … are the symbols to the right
The empty pairs “
(,)” represent the continuations of the tape, filled with underscore symbols (“
_”). They are expanded on demand.
All transitions are defined in the machine header using the syntax
#define CURRENT_SCANNED (WRITE, MOVEMENT, NEXT)
CURRENTis the current state
SCANNEDis the symbol at the current position
WRITEis the symbol to be written to the tape
L” for left, “
R” for right, or nothing
NEXTis the next state
There must be a state “
A” defined, which becomes the initial state of the machine.
To halt the machine, use the keyword “
break” as in
#define A_1 (2, break)
© Copyright 1984-2016,
Leo Broukhis, Simon Cooper, Landon Curt Noll
- All rights reserved