P Article Index for
P 		 

Information About

P
  CATEGORIES ABOUT P′′
   
esoteric programming languages
   
APPAREL
BABY
BEAUTY
BOOKS
CAR TOYS
CELL PHONES
DVD'S
ELECTRONICS
GOURMET FOOD
GROCERIES
HEALTH & PERSONAL
HOME & GARDEN
JEWELRY
MUSIC
MUSIC INSTRUMENTS
OFFICE PRODUCTS
SOFTWARE
SPORTING GOODS
TOOLS & HARDWARE
TOYS
VIDEO GAMES
SHOPPING HOME
MORE SHOPPING...




DEFINITION

\mathcal{P}^{\prime\prime} (hereafter written P′′) is formally defined as a set of words on the four-instruction alphabet {R, λ, (, )}, as follows:


Syntax

# R and λ are words in P′′.
# If ''p'' and ''q'' are words in P′′, then ''pq'' is a word in P′′.
# If ''q'' is a word in P′′, then (''q'') is a word in P′′.
# Only words derivable from the previous three rules are words in P′′.


Semantics

  • {a0, a1, ..., a''n''}(''n'' ≥ 1) is the tape-alphabet of a Turing Machine with left-infinite tape, a0 being the ''blank'' symbol.

  • R means move the tape-head rightward one cell (if any).

  • λ means replace the current symbol a''i'' by a''i''+1 (taking a''n''+1 = a0), and then move the tape-head leftward one cell.

  • (''q'') means iterate ''q'' in a While Loop , with condition that the current symbol is not a0.

  • A program is a word in P′′. Execution of a program proceeds left-to-right, executing R, λ, and (''q'') as they are encountered, until there is nothing more to execute.



RELATION TO OTHER PROGRAMMING LANGUAGES


  • Brainfuck (apart from its I/O commands) is a minor informal variation of P′′. Böhm 1 gives explicit P′′ programs for each of a set of basic functions sufficient to compute any Computable Function , using only (, ) and the four words r ≡ λR, r′ ≡ r''n'', L ≡ r′λ, R. These are the equivalents of the six respective brainfuck commands , +, -, <, >.



EXAMPLE PROGRAM

Böhm 1 gives the following program to compute the predecessor (''x''-1) of an integer ''x'' > 0:

: R ( R ) L ( r' ( L ( L ) ) r' L ) R r

which translates directly to the equivalent brainfuck program

: > > < −  [ < [ < ] −  < ] > +

  • 22 + 1---21 + 2---20.) At the beginning and end of the computation, the tape-head is on the a0 preceding the digit-string.



REFERENCES

# Böhm, C.: "On a family of Turing machines and the related programming language", ICC Bull. 3, 185-194, July 1964.
# Böhm, C. and Jacopini, G.: "Flow diagrams, Turing machines and languages with only two formation rules", CACM 9(5), 1966. (Note: This is the most-cited paper on the Structured Program Theorem .)


EXTERNAL RESOURCES

  • The Fm languages are variations of P′′ as adapted to Turing machines with a right- (or optionally both-ways-) infinite tape.