Behaviour of Algorithms at Time at Infinity

[Dragonfall]

Where might I learn more about the behaviour of algorithms given an infinite amount of time, if such a question makes sense?

 

[neurocomp2003]

no such a question doesn't make sense.
However if you wanted to see what your up against take a look at courses(outlines) for Computability or Complexity Theory or THeory of Computation.

What you'd probably be interested in may be Dynamical Systems Theory and whether it can be applied to Algorithms. Basically can you discover patterns in algorithms like periodicity.

 

[Hurkyl]

I should clarify -- as stated the question doesn't make sense. But it is possible to ask other similar questions that do make sense.

The problem is that algorithms are iterative things, and you can't reach an infinite ordinal through iteration alone.

So, if you want to talk about behavior at infinity (as opposed to asymptotic behavior), you will have to devise some sort of limit.


The first alternative that springs to my mind is a Turing machine (an "idealized computer") equipped with a write-only output tape. While you generally can't ask about the behavior of the machine itself after infinitely many steps, you can ask about the contents of the output tape.


A second thing that springs to mind is the notion of transfinite induction, although it's not really an algorithm. (though it is the appropriate generalization in certain contexts)



Did you have any particular application in mind? I suspect it's better to use some approach other than trying to study an algorithm's behavior "at infinity", and maybe we can suggest something if we know what you're trying to do.

 

[Dragonfall]

I thought about the 'behaviour' of the following programs 'at infinity', and I thought they must be different. I'll just write as if 'at infinity' is defined:

1. Any simple loop (while(1) blah)
2. Print the natural numbers in succession until all natural numbers have been exhaulsted.

Seems to me the first one will not stop at infinity and the second one will.

 

[neurocomp2003]

Oh man i just burned my throat with grapefruit. And its making me cough badly

Anyways Dragonfall: how will the second one stop at "infinity"
Computer memory is finite though the set N is infinite. Actually there would be two ways to do this. One will stop(finite) and the other will not stop(infinite)

The first is to create a Natural Class with N bits to store the number.
Once the maximum number has been reached the computer will stop. Clearly that number isn't infinite.

The second method is to just use the succession operator (or simply +1)repeatedly and this will go into an infinite loop because there are no checks for overflow.

 

[0rthodontist]

I thought about the 'behaviour' of the following programs 'at infinity', and I thought they must be different. I'll just write as if 'at infinity' is defined:

1. Any simple loop (while(1) blah)
2. Print the natural numbers in succession until all natural numbers have been exhaulsted.

Seems to me the first one will not stop at infinity and the second one will.

Well, one thing you can say about those two is that in the first one, the program's state repeats, and in the second one the program's state does not ever repeat. As far as "stopping at infinity" goes, I think what probably captures your intent is that in the second one it is possible to put the configurations of the program in 1-1 correspondence with the integers--"exhausting" them--and in the first one it is not.

 

[Dragonfall]

Suppose you have infinite memory, then the second one will stop since it has printed all integers in sucession, and has printed an infinity of them -- 'exhaust' them, so to speak.

This is a thought experiment, there's no point to actually doing this on a computer with 'finite memory'.

 

[neurocomp2003]

even if you have infinite memory what is your condition to terminate? You cannot just say for(0...infinity) since in most computer programs infinity is actually a finite number. If you have infinite memory then you can write a program that will never terminate based on either a N class or the succ() operator

 

[0rthodontist]

But it won't actually stop. It does exhaust all the integers, but it never actually reaches "infinity." I don't think there's any way to get closer to saying that it stops.

You could try saying, run both programs so that the iteration number is greater than any integer. Then there is no possible state that the second one can be in, since any such state would lead to its printing an integer it must have already printed. But the first one could plausibly be in one of the few states it has available to it, since nothing about those states says much of anything about the number of iterations, so maybe it could still be "running" after an infinite amount of time. However, this argument is flawed because the contradiction also holds for the first one; despite the configurations repeating, you can still assign numbers to them in their order of appearance, creating a sequence of configurations. And if you have run the program for a number of times greater than any integer, it can't be anywhere in that sequence. So it's a meaningless supposition.