Nanofunge
Nanofunge, like Nopfunge, is a fungeoid. It's a 2D esoteric programming language base on 3 commands which is a "subset" of Befunge. The goal of it is to discover the minimum number of commands to make a direction-only language Turing-complete.
Language Overview
Nanofunge, like Nopfunge, is made out of a two-dimensional playfield which can have any size. The infinite repeating part's size is said at the start. For example,
5 5 3 3 C C C< CCC C C<<C< C C
expands to
C C C C C C C C C C C< C< C< C< C< C< C< C< C<... CCC CC CC CC CC CC CC CC CC C... C<<C<<C<<C<<C<<C<<C<<C<<C<<C<... C C C C C C C C C C... CCC CC CC CC CC CC CC CC CC C... C<<C<<C<<C<<C<<C<<C<<C<<C<<C<... C C C C C C C C C C... CCC CC CC CC CC CC CC CC CC C... C<<C<<C<<C<<C<<C<<C<<C<<C<<C<... C C C C C C C C C C... CCC CC CC CC CC CC CC CC CC C... C<<C<<C<<C<<C<<C<<C<<C<<C<<C<... C C C C C C C C C C... CCC CC CC CC CC CC CC CC CC C... C<<C<<C<<C<<C<<C<<C<<C<<C<<C<... C C C C C C C C C C... CCC CC CC CC CC CC CC CC CC C... C<<C<<C<<C<<C<<C<<C<<C<<C<<C<... C C C C C C C C C C... CCC CC CC CC CC CC CC CC CC C... C<<C<<C<<C<<C<<C<<C<<C<<C<<C<... C C C C C C C C C C... CCC CC CC CC CC CC CC CC CC C... C<<C<<C<<C<<C<<C<<C<<C<<C<<C<... C C C C C C C C C C... CCC CC CC CC CC CC CC CC CC C... C<<C<<C<<C<<C<<C<<C<<C<<C<<C<... C C C C C C C C C C...
Instructions
Nanofunge has 3 instructions:
| Command | Description |
|---|---|
| (Space) | NOP |
| < | set direction to left |
| C | turn clockwise |
Program halts on 2 consecutive ineffective <'s (< when direction is already left)
Computational Class
Turing-complete, because it can be substituted from Nopfunge. Nopfunge space and < are trivial. halt:(4 empty lines before)
C<<<
<<<<<<
C C
CC CC
right:
CC CC
C C
C C<
C C
CC<C
CC< CC
CC
C C
up:(2 empty lines before)
CC C CCCC
C CC C
CC< <C
C C
CC C
CC CC
down:(1 empty line before)
C C
C CC CC
C C< C
CC< <C
CCCC C
C CCC
This proves that Nanofunge IS Turing-complete.
(All conversions accept the directions from the 5th row/column)
See also
- Yoctofunge, minimalization of Nanofunge.