patternMinor
Termination in infinite-time
Viewed 0 times
infiniteterminationtime
Problem
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!
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!
Solution
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
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
Context
StackExchange Computer Science Q#35598, answer score: 4
Revisions (0)
No revisions yet.