Dear Peter:

We are exploring generic mathematical models for recursions and iterations rather than their traces at run-time. By a generic mathematical model, a recursive or iterative structure may be directly derived rather than individually designed as problem-specific techniques in programming.

Actually, it’s one of the fundamental problems in computing. We had difficulty to do so or the current mathematical means were not sufficient. If you perceive there is such a generic mathematical model (not expressed in any programming language), just show us. The trace models are only semantic models (or interpretations) of them rather than mathematical models themselves. (BTW, I was a visiting professor at Oxford directly working with Prof. Tony Hoare in 1995. That‘s why I am posting a question like this.)

Best,

Yingxu

Yes, we do have the entity known as “cars” and know their semantics and behaviors by driving. However, we had no mathematical models of a generic car (except that one might consider a CAD model as a mathematical model).

So do the basic control structures of recursions and iterations in computing. We had already known their behaviors and semantics (in different interpretations including the reductive semantics [Wang, 2006/07/08/10; ICIC, http://www.ucalgary.ca/icic/]), as well as we can run then in programs. However, we have not yet got the generic (abstract) mathematical model of them? The various semantic models just tried to interpret what they meant rather than what they are with more complicated explanation than the entities themselves in programming. Therefore, the question is what a recursion or iteration is in a mathematical structure so that any programming implementation in any languages can be treated as an instance of it by deduction. If one happened to look into linguistics, one would agree that probably listeners could not be convinced by any kind of semantics where the explanation is more complicated that the entity itself.

This is a sign of some immature theories in computing where fundamental issues were overlooked or treated as given. Although the missing of mathematical models is not serious for the former (cars), it is crucial for the latter (basic structures of computing).

@Peter: You perhaps over underestimated the hardness of the problems aiming at seeking a simpler (better) solution.

With regards to what is a generic mathematical model on a certain set of problems, you’d look some well know ones such as those of Newton and Einstein:

... F = ma .......... (1) and,

... E = mC^2 ...... (2)

You don’t need a semantic model to replace the above mathematical models, do you! There is no confusion about what it is and what it means (semantics), isn’t it? Were these not the basic philosophy that PRG professors taught you? Actually, it’s so curious to know your opinion that a formal semantics about an entity (such as recursion and iteration) may be proposed before the establishment of a formal model for the entity itself. Further details may be found in Semantic Algebra and Cognitive Linguistics [Wang, 2012; ICIC, http://www.ucalgary.ca/icic/].

I perceive that formal semantics are the pinnacle of software engineering theories. However, a comparative study on major forms of them would result in the observation that there are astonishing inconsistencies, too much tautology, and a too strong tendency to explain the semantics of simple constructs such as iteration and recursion by more complex settings. That’s why Prof. Tony Hoare had preferred to address on “The Empire’s Old Clothes” in his Turing Award presentation.

Since this thread had perhaps been abused, further discussions on the mathematical models of iterations and recursions have been moved under the Question on “What are the differences between iterative and recursive structures in computing? Are the latter a special case of the former or vice versa?”