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

Question

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?

Explanation / Answer

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.

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.