153 - The Hofstadter Sequence : A Paradigme for Non-uniform Reasoning

N. Lygeros

The Douglas Hofstadter sequence is, to some extent, a deformation of Fibonacci’s. Itrepresents a generic case of the existence of an abstracted relation between the immediatefuture and the remote past. With the opposition to the mentality generated by the theory ofdifferential equations, we find in this sequence a fractal aspect whose complexity is interpreteda priori as indeterminism because this recursive process seems to have a chaotic behavior. Ourgoal is to show that this process, ultimately deterministic and understandable, constitutes aparadigm for non-uniform reasoning.

One of the characteristics of the reasoning described as intelligent is the synchronicsynthesis of knowledge to solve a given problem. It seems that for relatively elementaryproblems – for example, exercises or fast tests – this characteristic is amply sufficient for theirresolution. The really difficult problems, however, require the use of diachronic synthesis. Thismethod, although very expensive in terms of memory, is essential. Indeed, its power not onlymakes it possible to overcome the difficulties encountered, but also to completely understandthe complexity of the problems.

Within this framework, let us attempt to analyze the surprising character of the fastresolution of a complex problem. It is obvious that this type of resolution can come from apreliminary knowledge of a problem and an analogous resolution. Let us therefore excludethis case from our study, a choice which all the more highlights the surprising characterof the resolution. Let us propose, then, a possible explanation of this phenomenon: fastresolution appears surprising for one observing the solver because the observer first carriesout an implicit inference, knowing the continuity of the reasoning in cognitive space. Thisinference implies for the observer that there is no essential phase shift in the reasoning of thesolver. Thus, for the observer, the immediate outcome of the intellectual advance could evendepend only on the present. Nevertheless, we now consider a type of problem whose heuristicmodel corresponds to the Douglas Hofstadter sequence. It is clear that the value sought fora 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 acertain total way, allows the determination of the required value. And it is precisely thismethod of the solver that surprises the observer: the solver was not locally fast but differentin an essential way.

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