The Hofstadter Sequence : A Paradigme for Non-uniform Reasoning

N. Lygeros

The Douglas Hofstadter sequence is, to some extent, a deformation of Fibonacci's. It represents a generic case of the existence of an abstracted relation between the immediate future and the remote past. With the opposition to the mentality generated by the theory of differential equations, we find in this sequence a fractal aspect whose complexity is interpreted a priori as indeterminism because this recursive process seems to have a chaotic behavior. Our goal is to show that this process, ultimately deterministic and understandable, constitutes a paradigm for non-uniform reasoning.

One of the characteristics of the reasoning described as intelligent is the synchronic synthesis of knowledge to solve a given problem. It seems that for relatively elementary problems - for example, exercises or fast tests - this characteristic is amply sufficient for their resolution. The really difficult problems, however, require the use of diachronic synthesis. This method, although very expensive in terms of memory, is essential. Indeed, its power not only makes it possible to overcome the difficulties encountered, but also to completely understand the complexity of the problems.

Within this framework, let us attempt to analyze the surprising character of the fast resolution of a complex problem. It is obvious that this type of resolution can come from a preliminary knowledge of a problem and an analogous resolution. Let us therefore exclude this case from our study, a choice which all the more highlights the surprising character of the resolution. Let us propose, then, a possible explanation of this phenomenon: fast resolution appears surprising for one observing the solver because the observer first carries out an implicit inference, knowing the continuity of the reasoning in cognitive space. This inference implies for the observer that there is no essential phase shift in the reasoning of the solver. Thus, for the observer, the immediate outcome of the intellectual advance could even depend only on the present. Nevertheless, we now consider a type of problem whose heuristic model corresponds to the Douglas Hofstadter sequence. It is clear that the value sought for a given row does not depend on those of immediately close rows. In this type of problem, a local knowledge proves to be insufficient and only a diachronic synthesis, and thus, in a certain total way, allows the determination of the required value. And it is precisely this method of the solver that surprises the observer: the solver was not locally fast but different in an essential way.

Thus our paradigm of non-uniform reasoning explicitly shows that the difference between a reasoning based on a diachronic synthesis and another is qualitative rather than quantitative. Moreover, when the solver belongs to one of the fundamental categories (cf our article: M-classification) this qualitative difference leads to a concept incomparable in cognitive space.

free counters