en>LutzL: Disambig: Fourier [domain] -> Fourier analysis

2013-04-29T15:18:27Z

Disambig: Fourier [domain] -> Fourier analysis

New page

{{Infobox programming language
| name = P′′
| paradigm = [[Imperative programming|imperative]], [[Structured programming|structured]]
| released = 1964
| designer = [[Corrado Böhm]]
| typing = untyped
| dialects = [[Brainfuck]]
| influenced = [[Brainfuck]]
}}
'''P′′''' is a primitive computer [[programming language]] created by [[Corrado Böhm]]<ref name="bohm1964">Böhm, C.: "On a family of Turing machines and the related programming language", ICC Bull. 3, 185-194, July 1964.</ref><ref name="bohm1966">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]].)</ref> in 1964 to describe a family of [[Turing machine]]s.

==Definition==
<math>\mathcal{P}^{\prime\prime}</math> (hereafter written '''P′′''') is formally defined as a set of words on the four-instruction alphabet {<tt>R, λ, (, )</tt>}, as follows:

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

===Semantics===
* <tt>{a0, a1, ..., a''n''}(''n'' ≥ 1)</tt> is the tape-alphabet of a [[Turing machine]] with left-infinite tape, a0 being the ''blank'' symbol.
* <tt>R</tt> means move the tape-head rightward one cell (if any).
* <tt>λ</tt> means replace the current symbol <tt>a''i''</tt> by <tt>a(''i''+1) [[Modulo_operation|mod]] (''n''+1)</tt>, and then move the tape-head leftward one cell.
* <tt>(''q'')</tt> means iterate <tt>''q''</tt> in a [[while loop]], with condition that the current symbol is not <tt>a0</tt>.
* A program is a word in P′′. Execution of a program proceeds left-to-right, executing <tt>R</tt>, <tt>λ</tt>, and <tt>(''q'')</tt> as they are encountered, until there is nothing more to execute.

== Relation to other programming languages ==
* P′′ was the first "GOTO-less" imperative [[structured programming]] language to be proven<ref name="bohm1964" /><ref name="bohm1966" /> [[Turing-complete]].

* The [[brainfuck]] language (apart from its I/O commands) is a minor informal variation of P′′. Böhm<ref name="bohm1964" /> gives explicit P′′ programs for each of a set of basic functions sufficient to compute any [[computable function]], using only <tt>(</tt>, <tt>)</tt> and the four words <tt>r ≡ λR, r′ ≡ r''n''</tt> (<tt>r''n''</tt> means <tt>rrrrr...rr</tt> [<tt>''n''</tt> times])<tt>, L ≡ r′λ, R.</tt> These are the equivalents of the six respective brainfuck commands <tt>[, ], +, -, <, ></tt>. Note that since <tt>a''n''+1 = a0</tt>, performing <tt>r</tt> ("increment" symbol in current cell) <tt>''n''</tt> times will wrap around so that the result is to "decrement" the symbol in the current cell by one (<tt>r′</tt>).

== Example program ==
Böhm<ref name="bohm1964" /> 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

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

The program expects an integer to be represented in ''[[bijective numeration|bijective base-n]]'' notation, with a1, ..., a''n'' coding the digits 1,...,''n'', respectively, and to have an a0 before and after the digit-string. (E.g. in bijective base-2, the number eight would be encoded as a0a1a1a2a0, because <tt>8 = 1*22 + 1*21 + 2*20</tt>.) At the beginning and end of the computation, the tape-head is on the a0 preceding the digit-string.

== References ==
{{Reflist}}

{{DEFAULTSORT:P}}
[[Category:Models of computation]]
[[Category:Academic programming languages]]
[[Category:Experimental programming languages]]

Second-generation wavelet transform - Revision history

en>LutzL: Disambig: Fourier [domain] -> Fourier analysis