Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Writing pseudo-code for algorithms is common practice in the applied mathematics literature. It is also often the case that the ideal input of an algorithm is an infinite set, for example it could be a positive-dimensional algebraic variety over $\mathbb{C}$. However practical algorithms only take as input a finite sample of this infinite ideal set. As another example, image processing algorithms take as input the pixels of a digital image, however the ideal input is a continuous object, i.e. the actual physical scene that the digital camera is attempting to capture.

So, it might be of interest, in order to understand the theoretical properties of such algorithms, to develop abstract versions of them, in the sense that their inputs and outputs are theoretical objects, not necessarily subject to computation. These algorithms might also require operations that again might not be computable, for example, we might have statements of the form "$while \, \, \, A \neq B \, \, \, do \, \, \, A \gets A\cap B$", where both $A,B$ are infinite sets. Notice that in general, if one is given $A$ and $B$, it is not possible to check the validity of the condition $A \neq B$. In fact, in general, one can not even receive either $A$ and $B$, because they are infinite!

So my question is: is it scientifically correct to write abstract algorithms in the above sense? Have such algorithms appeared in the literature? If not, then how can one abstract an algorithmic process that operates mathematically on abstract, non-tangible objects?

share|improve this question

3 Answers 3

up vote 1 down vote accepted

One way to write down algorithms that work with infinite/non-computable objects is to assume that you some kind of "oracle" that can perform the required computation. For your example, you could assume that you have some "magic" oracle function that checks whether $A \neq B$ that can somehow be invoked by your algorithm.

For more details, see, e.g., http://en.wikipedia.org/wiki/Oracle_machine.

share|improve this answer
    
This is very interesting! How about the input to an algorithm being an infinite set? How do we circumvent the problem that one actually cannot supply any algorithm with an infinite input? –  Manos Oct 8 '13 at 22:19
    
That's a bit tricky, because, strictly speaking, you can't do that. One possible solution would be to assume some more oracles that model the characteristic functions of infinite sets, and pass those around. –  Johannes Kloos Oct 9 '13 at 6:30
    
What is the characteristic function of an infinite set? –  Manos Oct 10 '13 at 0:23
    
The same thing as a characteristic function of a finite set (a function that returns true if called with an element of the set, false otherwise). Admittedly, you'll have to figure out a good input data type; it is possible to encode infinite types inductively, though. –  Johannes Kloos Oct 10 '13 at 7:43
    
Another thing: You should probably look at how Coq allows you to define arbitrary functions and write "algorithms" with them. –  Johannes Kloos Oct 10 '13 at 7:44

The analysis of algorithms began over 2,000 years ago with the kind of abstract algorithm you describe. Here is Proposition X.2 of Euclid's elements (with acknowledgments to the translation you can find at http://farside.ph.utexas.edu/euclid/Elements.pdf):

If the remainder of two unequal magnitudes never measures the magnitude before it, when the lesser magnitude is continually subtracted in turn from the greater, then the original magnitudes will be incommensurable.

In modern terminology, the "magnitudes" are positive real numbers. What Euclid is describing is a process whereby you take two positive real numbers $A$ and $B$ say and repeatedly subtract the smaller from the larger until they become equal. The conclusion is that $A$ and $B$ are incommensurable, i.e., $A/B$ is irrational, if this process never terminates. The termination test ($A \not= B$) for this algorithm is not computable.

share|improve this answer
    
1) This is interesting. So you are saying that having conditions like "while $A \neq B$...", where $A,B$ are infinite sets is ok? 2) Do you know of any examples where an algorithm takes as input an infinite set and does set-theoretic operations on it? 3) Another concern is that Euclid's elements is essentially an ancient document. I am more interested in references from modern theoretical computer science. –  Manos Oct 8 '13 at 21:49
    
(1): yes - there is no mathematical problem with reasoning about computational processes involving calculations that cannot be performed by a Turing machine. For (2) and (3) the work on computable numbers by Weyrauch and others should be of interest, see en.wikipedia.org/wiki/Computable_number) and the references there. –  Rob Arthan Oct 8 '13 at 22:05

Newton's algorithm finds a root of an equation in terms of abstract computation, but the initial conditions might be not representable well as a floating point number, and the resulting computations for subsequent approximations might not be representable well as a floating point number. So this might be an example of interest to you. Newton's method could potentially fail if the numeric precision in arithmetic calculations isn't "arbitrarily large". But it works with exact arithmetic, under mild assumptions about the function and starting guess.

share|improve this answer
    
The difference from the case that i am describing, is that all the steps in Newton's algorithm are computable or representable. The accuracy of the computation or representation is another matter. So, Newton's algorithm does not fit to the type of algorithm that i am describing, otherwise, our world would not be as it is :) –  Manos Oct 8 '13 at 20:54

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.