- If a program description can be represented as a sequence, then what is the best structure to entail program descriptions which self-modify?
- There must exist a relationship between the structure in (1) and recursive functions. Can you describe this relationship in detail, especially as it pertains to decidability (c.f. Rice's theorem)?
Thank you in advance.
This depends on which features of self-modification you're interested in modelling, I think.
My immediate ideas for a formalism would be either to model a Von Neumann architecture with some appropriately simple instruction set, or to define a formal semantics for some kind of idealized Lisp with some reflection features.
In the first case, the representation of a program would be a sequence denoting the content of the memory before the program begins to run (and possibly self-modify). By convention, input to the program would be placed immediately after itself.
In the second, a program could potentially just be an s-expression that the machine starts to evaluate. Because of reflection, it could start by defining some functions if it wants to, and later call them.
Neither of these options properly extend the class of representable functions. It ought to be clear that any of the usual non-self-modifying models of computation can simulate these models, and conversely a program in either of the models may still choose not to self-modify, so everything that can be programmed in a more usual model can still be programmed in one of these.
In fact, both of them easily seem to satisfy the modest requirements about enumerations of computable functions that allow things like Rice's theorem to be proved for them.