Roy Simpson writes:
---
Nigel,
Speaking of models of computation (as we sometimes do), I have off and on wondered about the following model. Reading an old (online) paper by Engelbart has reminded me of it again. I wonder whether you think this idea as any merit.
Normally in digital computation the core construct is:
State1 -----> Action A1 ------> State2
This is the basis of all the models whether Finite State Machine or Turing machine. However we know that in some modelling situations (ranging from robot modelling to Project Planning) we would write an expression like this and then say:
"to undertake Action1 we need to do activities A11, A12, ..., A19 (perhaps in sequence, perhaps in parallel)".
So we have to decompose the action A1 into subactions. As a separate but perhaps related point we might want to decompose State1 and State2 into substates as well: State11, State12, ..., State19; State21, State22, ..., State29.
Either way we have decomposed the process definition above. If we iterate this then we go to as much detail as needed in the Project Plan etc. So we generally assume that there is some atomic set of subsub Actions and subsub States from which the whole system can be built up. However what if such atomic actions (resp. States) didn't always exist? Then we would have e.g. Actions like:
Action12323215436....
where the notation indicates some concept of subAction of the next integer (so it is a sub...Action of Action1 and of subAction12). This looks like a real number (or some exotic like a hyperreal) labeling the Action (and corresponding States if we do them too).
If this can be made consistent it is a little bit analogous (maybe) to the non-foundation axiom sometimes discussed for Set Theory, so that some sets have infinite descending chains of membership. Also it looks more like a continuum model of computation rather than the usual discrete ones. Anyway it is something to think about to see if a consistent model can formed here. Any thoughts?
Roy.
--- Reply ---
So you presented various mathematical structures here:
1. A tree with finite branching but at least one branch of infinite depth.
2. As above but with at least one infinite branch.
3. A sequence of nodes which is in one-to-one correspondence with the digits of an infinite (non-recurring?) real number.
You want to associate an action (a computational step) with each of the nodes of the trees in (1) and (2) and with each digit in (3).
So the question is: are there any interesting computation-theoretic issues associated with any of these structures?
Well the first reminds me of automated theorem-proving where the program does a depth first search looking for a proof of the root-node proposition. The case of an infinitely-deep branch corresponds to a non-terminating compution of course, an indication that the proposed theorem is not actually true (it might be undecidable). I seem to recall from the days when I studied this that it was recommended to start two copies of the theorem-prover: one to prove P and the other to prove not-P. You'd then get tripped up only by undecidability.
The second case doesn't normally arise in theorem-provers as there is a finite set of axioms and theorems to apply at each node.
More exotically one could consider models of computation where as the actions (computational steps) got "smaller" the time to compute them decreased commensurately. Then infinite computations could terminate in finite time. This is so unphysical in digital terms that I guess few people think about it. However there might be continuum models of computation (what we used to call analogue computation) where something interesting could be said, rather reminiscent of the way number-theoretic resultsd are proved via an excursion through the reals or the complex numbers.
Definitely worth a second look!
N.
