Pimc Pifl Pire

Three proposed instructions (special forms, functions, etc.) which if implemented as specified, would give a programming language super-Turing computational power--the ability to solve problems in finite time that a Turing machine cannot. Naturally, it is impossible to build hardware to implement these instructions, so they are of theoretical interest only. But if they were added to FlooP, one might have GlooP (see BloopFloopAndGloop).

It is not claimed herein that these instructions are comprehensive; there may be additional instructions which would add computational power. Nor is it claimed that this is a minimal set; I'm sure one could be implemented in terms of the other two.

But here they are:

Pimc (Parallel Infinite MapCar)

Example syntax:


        pimc  in  do

Behavior: For all elements of , apply the function specified in . is provided as a convenience so non-FunctionalWeenies don't have to write lambda-expressions all over the place. So far, this sounds like an ordinary mapcar/foreach expression...however:.

The collection may be infinite. (Of any cardinality; though it might be a useful exercise to explore the effects of limiting ourselves to infinite sets with the cardinality of the integers).

All elements of the collection are handled in parallel. Including infinite sets.

If takes a finite amount of time to execute for all possible values of ; then any pimc statement using also takes a finite amount of time; including those on infinite sets.

Note that can be any expression describing a collection (of any shape--set, list, etc.). It could be a simple enumeration of elements, a ListComprehension, or another expression using these three operators.

Pifl (Parallel Infinite FiLter)

Example syntax:


        pifl  in  where

Behavior: For all elements of , apply the Boolean function specified in . If the predicate returns true; the element is a member of the output collection; otherwise it's not. (We'll ignore divergence and exceptions for now).

All the other rules for pimc apply to pifl; replacing with where appropriate. In particular, if runs in finite time, then a pifl using shall run in finite time, even on an infinite collection.

Finally,

Pire (Parallel Infinite REduce)

Example syntax:


        pire  using

Reduces a collection down to a scalar value, using which must be a commutative, associative function defined over the elements of . If has cardinality greater than one; two elements are selected (non-deterministically) and provided as arguments to ; pire is then re-run on the collection containing the result and the remaining elements. If has cardinality equal to one; its single element is returned.

Like the others, all of this magically happens in parallel.

pire may be more problematic than the other two, as all computations done by pifl and pimc could be done in parallel, given an infinite number of processing elements. There is no dependency among computations. pire does have dependency between computations, on the other hand; it could be argued that even with an infinite number of computational elements pire still takes an infinite time on an infinite collection. (The optimal computational structure for pire would take O(lg x) for a collection of size x; lg infinity is still infinity). However, since everything here is magic anyway; we can pretend pire happens in finite time. It would be interesting to allow pimc and pifl, but not pire.

One thing that should be noted is that it is not possible to implement pimc, pifl, or pire using is an unbounded stream as a source for , for the simple reason that the act of processing a stream is, by nature, sequential; even if the individual operations were run as separate threads of execution, there would still be a finitely small sequence delay between the beginning of operation on stream object N and the beginning of operation on stream object N+1 (this is a processing delay, and not related to the speed at which the stream provided the data). As a result, the collection is not homogeneously parallelized, and an infinite set cannot be processed in a finite amount of time in this manner. This may seem obvious, but it highlights a common misunderstanding in the use of stream operations for processing 'unlimited' data sets. - JayOsako

If you have these, lots of things become possible; here is a program (in pseudocode) which proves FermatsLastTheorem. The expression INTEGERS is the set of all integers (a countably infinite set, obviously). The expression PRODUCT forms the named Cartesian product of the provided sets, which might be infinite.


        program Fermat is [

        def PositiveIntegers := pifl x in INTEGERS where (x>0) ;


        def Exponents := pifl x in INTEGERS where (x>2);


        def FermatUniverse := PRODUCT [

        a: PositiveIntegers;

        b: PositiveIntegers;

        c: PositiveIntegers;

        n: Exponents

        ];


        def FermatSolutions := pifl q in FermatUniverse where (

        (q.a ** q.n) + (q.b**q.n) == (q.c ** q.n));


        if (FermatSolutions.size() == 0) 	then [write "Fermat was right"]	else [write "Fermat was wrong"];

        ]

Pimc and pifl are sufficient to crack any crypto system instantly. The set of possible keys for most crypto systems isn't even infinite.

Pimc and pifl could also be used to compress data perfectly. Since Turing machines are countably infinite, Pimc and Pifl would be able to find the smallest Turing machine, plus input data, that would produce a given output. (You could optionally require that the output be generated by the Turing machine within a certain amount of time.) Used in this way, pimc and pifl would be able to replace any pseudo-random bit sequence with its generator (provided the generator was smaller than the data given). Thus, they would be able to distinguish pseudo-random bits from genuinely random bits.

It should be possible to use Pimc and pifl to determine whether or not P equals NP.

(Some of these things might require Pire or other operations such as parallel-infinite-collect, which would operate similarly to pimc but with each input being replaced by a variable number of outputs.)

What's the problem with pimc? Why not start a daemon that sits on the collection and transforms its members at the time they are accessed? That would be a finite overhead.

This leads to the exact same situation I discussed above in regards to performing a mapchar on an unbounded stream: it is not truly parallel. The whole point of 'pimc' et al. is that they must operate on the all elements of an infinite data set simultaneously. Otherwise, they still remain bound by the limits of sequential computation.

The key matter is this: there are a large number of computations and tests which can be performed in finite time for a single data point, but whose properties cannot be demonstrated for all possible cases, because doing so would require operation on an infinite number of data points. - JayOsako

Pimc could be faked using lazy evaluation, but pifl and pire could not.

Not with the result it is intended to achieve; keep in mind that we are not discussing applied programming, but rather, the theoretical limits of sequential computation. The issue is not whether you can process an indefinite list; it is whether you can process an infinite list in a finite time, on a finite number of processors. While a lazy stream could 'fake' this for a finite data collection, processing an infinite data set would require either an infinite amount of time, or an infinite number of processors (one for each data element).

Of course, there are other ways of 'faking' the results of these functions as well: integrals, for example, are essentially a limited form of pire, done by taking advantage of certain regularities in the equations. But that misses the point, which is that to process each individual element of an infinite list requires at least one infinite resource. - JayOsako

Wow! Google implemented it (well, almost). Take a look at http://labs.google.com/papers/mapreduce.html. They combined PimcPiflPire in a single operation, and they use it every day. -- AurelianoCalvo

On the one hand, I've got to give Google a lot of credit for it; that's one hell of an impressive achievement. On the other... it's a still finite number of processors operating on a finite amount of data, and as everyone knows, any finite value divided by infinity is infinitesimal.

Which is the whole point. There are some things which cannot be computed through brute force alone, because it would take an infinite amount of time and/or an infinite amount of processing power. You still couldn't use Google's mapreduce to test whether Euclid's proof of the infinitude of primes is correct or not, for example. -- JayOsako

How's


        def pimc(infiniseq, &doto)

        #Written in ruby because of it's easy definition of new statements...

        return InfiniteSeq.new do |index|

        doto.call infiniseq[index]

        end

        end

        #Here, an InfiniteSeq calculates the value at [index] from the indes.

        def pifl(infiniseq, &pred)

        return InfiniteSeq.new do |index|

        until pred.call( ret = infiniseq[index] )

        index = index + 1

        end

        ret

        end

Can't do Pire, obviously, but the others aren't that hard...

See also InfiniteNonDeterminism (of which this page is an 'implementation')

CategoryFunctionalProgramming, sort of