Question Concering Recursive Systems

[EricJRose83]

Heyo,

I'm not sure if this is the proper place to post this question, but as far as I could tell it's the closest place to appropriately do so. Anyways, here's the question;

Are all isolated, deterministic systems inherently recursive?

Keep in mind by isolated, I mean completely closed off and... self sufficient, with no external influences. I realize such a thing is practically impossible unless I'm talking about the system of all systems, i.e. the universe, which... I suppose I am. By deterministic, I mean hard, unforgiving determinism with no sympathy towards weaker forms of it, etc.

Thanks everyone!

 

[eigenperson]

I'm assuming that you don't really mean "recursive" but "recurrent"; that is, the same state happens over and over again. The technical term would be "eventually periodic".

If that's what you mean, the answer depends on the nature of the system.

If the system can have only a finite number of possible states, then the answer is yes, it must be eventually periodic. This is a well-known (though very simple) theorem in the study of finite state machines -- I don't know if it has an official name.

If the system can have an infinite number of possible states, then the answer is no, it need not be eventually periodic. Here is a simple example: A perfectly elastic billiard ball launched from one corner of a frictionless, square table at a slope that is not rational will have an aperiodic trajectory. Here I'm assuming that the position of the billiard ball can be specified by (x, y), where x and y are real numbers.

 

[EricJRose83]

I just meant that it repeats itself over and over again an infinite amount of times, the system never stops and is ultimately a sequential reiteration.

The theorem you're looking for I believe is the Poincare Recurrence Theorem.

As far as the system having a finite or infinite amount of possible states, well... I suppose that is another question entirely. I'm not referring to any system in particular, other than 'isolated, deterministic' systems. Key word here is isolated, completely isolated that is with neither input, nor output. A self contained causal system that doesn't rely on previous causal chains for it's existence.

Would any system that meets this standard end up repeating itself over and over again an infinite amount of times, or would it provide original sequencing for the length of eternity?

 

[EricJRose83]

I just find it hard to believe that any self-contained, isolated, deterministic, causal system would be anything else other than recursive given an infinite run cycle.

 

[eigenperson]

No, the Poincaré recurrence theorem is something different, though not entirely irrelevant.

And I did give you the correct answer: it does matter whether the number of states of the system is finite or infinite. If there are a finite number of states, your intuition is correct: the system must eventually fall into a repeating cycle. If there are an infinite number of states, your intuition is wrong: the system need not eventually fall into a repeating cycle.

Now, I gave you one example of a completely closed deterministic system that doesn't eventually repeat itself -- the billiard table -- but you might not be satisfied with that because, although it never returns exactly to the initial state, it does eventually arrive at a state arbitrarily close to the initial state (this is the conclusion of the Poincaré recurrence theorem). So I'll give a couple more that don't have that property.

Example 1:

State variable: n (integer)
Transition function: n → n+1

Obviously this doesn't ever repeat itself. Yet it's closed, isolated, deterministic, and all that. A pseudo-physical analogy might be two objects in a universe that exert no force on each other, and their relative velocity is directly away from each other.

Example 2:

This is a pattern in a well-known cellular automaton (Life) that is completely deterministic. Yet not only does the pattern not repeat itself, every cell in the entire universe individually exhibits aperiodic behavior.

 

[EricJRose83]

Thanks for replying, Eigenperson.

I hate to say this, but the examples you gave me didn't meet all of the listed requirements, mainly isolated and self sufficient. They all have an initial 'creation' input caused by their originator.

Also could you give me a layman's example of the billiard ball argument? Math isn't my strong suit.

Thanks.

 

[eigenperson]

There is a clever way, called the "unfolding method," to show that the billiard ball system is not periodic. You can find an explanation in this freely available copy of http://www.math.psu.edu/tabachni/Books/books.html by Tabachnikov, on page 26. Unfortunately, his explanation doesn't have a picture and uses technical terms, but I don't really have the artistic skills (or the time) to draw the picture.

But basically, the idea is: suppose that the billiard ball is at point P at time t0, and later returns to point P at time t1. Over this time period, the billiard ball moved "horizontally" across the table an integer number of times m, and moved vertically across the table an integer number of times n. Its slope must therefore be rational (this is handwaving, but true). So if the slope were irrational, it could never return to point P.

As for the point about the "creator," I don't get it. Obviously any system I name will be created by me. That's unavoidable.

If what you're complaining about is the fact that in Example 2, the system has a given initial state, then fine. Throw away Example 2 and look at Example 1 only. It doesn't matter what the initial state is, the system still has the same property. In fact, that system doesn't need to have an "initial state" -- it can be viewed as having existed forever. There is no input into the system -- it entirely runs itself.

If you still object, I don't understand why, so please give an example of a system that meets the requirements to your satisfaction, so that I can get a better idea of what your objection is.

 

[EricJRose83]

Well, all of the examples you gave are actually sub-systems, due to initial input. As a result they're neither isolated, nor self-contained. If a system was isolated and self-contained, would it then follow that all events in that system would sequentially reiterate themselves an infinite amount of times? I realize the creation of such a system is impossible, but if one existed...

I'm asking because I think if one did exist, the only way to excuse it's existence would be via a causality loop, where A causes B, B causes C and then C causes A, into and from infinity. All of the causes would be accounted for in the system then and they would each hold the virtue of being arbitrary with no initial or end cause. It would effectively be it's own universe.

 

[EricJRose83]

Given that, would it be fair to say that any system (not sub-system) would hold this property as well?

 

[verty]

Two equally sized balls in empty space moving away from each other. This never repeats because the distance keeps growing, but it is isolated and deterministic. So the answer to your question is, no.

 

[EricJRose83]

Well in theory this might work, I'm asking about reality though. In reality the answer to that question would rest with the shape the universe, which we're unsure of. If it was euclidian, then yes the balls would move away from each other forever. If it was elliptical then the balls would eventually intersect. If it was hyperbolic, then... how knows what. I'm sure there would be other variables involved as well.