Author:

• Name: Dominik Muth
  Location: DE - Federal Republic of Germany (Germany)

To build:

    make

To use:

    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

Try:

    ./try.sh

Judges’ remarks:

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!

Author’s remarks:

Preprocessor Turing Engine

Features

• Turing machine runs in preprocessor
• universal (unlimited configurable states, symbols, and tape)
• no #ifs or other conditional directives, only #defines
• no recursive #include
• single compiler run (no repeated preprocessing)
• no variadic macros
• verbosity levels:
  • V=0 (default) only prints the final tape
  • V=1 additionally prints one tilde character per machine step (slow)
  • V=2 additionally prints details on each machine step (slow; generates large files)
• make target run runs ./prog and filters a little statistics out of the verbose output
• X (defaults to 3) sets the maximum number of steps: M(X) ~ 8^X

Limitations

If the machine does not halt after M(X) steps, you will see unexpanded macros in the output.

Compiler warnings

If V=1 or V=2 is used, you may see “warning: string length is greater than the length '4095' ISO C99 compilers are required to support”.

Programming

Implementing your own Turing machine is easy. Take a look at the supplied header files for examples.

Tape Symbols

Every symbol used (except _) must be explicitly declared using

    #define sym_SYMBOL(sym, _SYMBOL) sym

Example:

    #define sym_1(sym, _1) sym

Tape

The initial content of the tape must be defined in the tape header using a triple like:

    #define tape ((((,),...l2), l1), c, (r1, (r2..., (,))))

• l1, l2, … are the symbols to the left
• c is the symbol at the current position
• r1, 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.

State Machine

All transitions are defined in the machine header using the syntax

    #define CURRENT_SCANNED (WRITE, MOVEMENT, NEXT)

where

• CURRENT is the current state.
• SCANNED is the symbol at the current position.
• The whitespace before the parentheses is significant.
• WRITE is the symbol to be written to the tape.
• MOVEMENT is L for left, R for right; don’t specify anything if you want no movement.
• NEXT is 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)

Primary files

• prog.c - entry source code
• Makefile - entry Makefile
• prog.orig.c - original source code
• try.sh - script to try entry
• machine_beaver_4_2.h - busy beaver Turing machine macros
• machine_champ_2_4.h - current champion Turing machine macros
• machine_chaos_5_2.h - chaos Turing machine cpp macros
• machine_cmplx_5_2.h - complex Turing machine cpp macros
• machine_count_5_2.h - counting Turing machine cpp macros
• machine_gcd.h - greatest common divisor Turing machine cpp macros
• machine_great_3_2.h - greater Turing machine cpp macros
• machine_ioccc.h - IOCCC Turing machine cpp macros
• machine_nop.h - minimal Turing machine cpp macros
• machine_ru_2_4.h - runner up Turing machine cpp macros
• machine_times2.h - multiply by 2 Turing machine cpp macros
• tape_15_50.h - tape cpp macros
• tape_77_55.h - tape cpp macros
• tape_empty.h - empty tape cpp macros
• tape_five.h - tape cpp macros

Secondary files

• 2015_muth.tar.bz2 - download entry tarball
• README.md - markdown source for this web page
• .entry.json - entry summary and manifest in JSON
• .gitignore - list of files that should not be committed under git
• .path - directory path from top level directory
• index.html - this web page

Jump to: top