4
$\begingroup$

Does it make sense to speak of algorithms that take an infinite amount of time to terminate?

In particular, suppose we have a loop with a bound function that is initially positive and is decreased by the loop body each time. Furthermore, suppose that termination of the loop implies that bound function is non-positive. (Ie almost all assumptions of The Invariance Theorem are satisfied.)

Here's the rub, initially the value of the bound function is the cardinality of the natural numbers.

What can be said in such situations?

Any help or direction is most welcome; thank you!

Improve this question
$\endgroup$
4
  • $\begingroup$ Generally, one considers an algorithm to be a well-defined process (implemented, say, by a Turing machine) that will halt in a finite number of steps for any input. It's perfectly possible to have a TM that never halts (say, for example, a TM that generates the hexadecimal digits of $\pi$ in order), but most people would say that such a machine doesn't implement an algorithm. $\endgroup$
    – Rick Decker
    Dec 22, 2014 at 16:21
  • $\begingroup$ What is "a loop with a bound function"? Sorry for my ignorance. $\endgroup$
    – babou
    Dec 22, 2014 at 19:42
  • $\begingroup$ @babou A bound function is an integer function bf such that before the loop we have, usually, bf > 0 and after the loop we have bf <= 0. That is, it is an integer-valued expression that depends on the program variables, such that it is decreased by each iteration of the loop body and is guaranteed to be non-positive if/when the loop terminates. $\endgroup$
    – Musa Al-hassy
    Dec 22, 2014 at 22:01
  • $\begingroup$ @Rick Decker: I think it's worth taking a vote. It seems odd to limit algorithms to the expressive power of primitive recursive functions by definition. $\endgroup$
    – reinierpost
    Dec 22, 2014 at 22:50

3 Answers 3

Reset to default
4
$\begingroup$

A big thing that is studied in higher type computability is infinite streams. Others have talked about hyper computation but this isn't quite the same. For starters the objects and functions studied in higher type computability are all things you can do in Haskell or some other such real programing language. These functions DO terminate in finite time thanks to laziness.

Exact real arithmetic is arithmetic that is performed on infinite binary streams or other kinds of infinite streams (dyadic digits and more commonly having both negative and positive digits). Addition of such streams terminates in finite time but produces another object which is infinite. The trick here is that the infinite streams are definable by computable functions that have finite construction. It turns out that classically there exist certain infinite streams that we can't define. For instance a computable real on the range $[0, 1]$ can be defined by a function $f : Nat \to Bool$. If we have an undecidable set $S$ then if we consider $f(x) = 1$ if and only if $x \in S$ then $f$ defines a real number but NOT a computable real number. It seems to turn out that there are no natural examples of such numbers coming up in practice however.

For more information take a look at one of my favorite blog posts: seemingly impossible functional programs

Improve this answer
$\endgroup$
3
$\begingroup$

What you are describing is a notion of hypercomputation. Several ways of making sense of infinite computation are described in the Wikipedia article on hypercomputation. The approach of Hamkins and Lewis seems particularly popular. There is no need to invoke a cardinal-valued variable though; you can just have a plain old infinite loop.

Improve this answer
$\endgroup$
3
$\begingroup$

Yes, there are plenty of models of computation on infinite data where computations go on forever. For example, ordinary finite automata can be adapted to deal with infinite strings, giving $\omega$-automata.

However, it doesn't make sense to talk about such computations terminating since terminate means "end" and an infinite computation doesn't do that. So the acceptance criterion for an $\omega$-automaton isn't as simple as "It accepts if it terminates in an accepting state". There are various ways of doing this. Conceptually, the easiest is the Büchi automaton, which accepts its infinite input if it visits accepting states infinitely often.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ However, infinite inputs (e.g., infinite strings for $\omega$-automata) do not imply termination in infinite time (e.g., acceptance conditions for Buchi automata). The OP is asking about terminations in infinite time. $\endgroup$
    – hengxin
    Dec 23, 2014 at 4:38
  • $\begingroup$ @hengxin And I address that point explicitly: "it doesn't make sense to talk about [infinite] computations terminating." Since it doesn't make sense to talk about termination, I give an example of what acceptance means. $\endgroup$
    – David Richerby
    Dec 23, 2014 at 8:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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