Re:On Two Views of Computation in Computer Science
by ankurdhama on Thursday September 01, 2016 @02:39AM
(#12403461)
I think you are confusing the word machine in this context. It is not the usual general purpose word machine that people use in every day life to denote a physical system. The word machine in context of model of computation means a specific type of "formal system" to describe computation. The problem of composition is about how this formal system does or doesn't support it.
Re:On Two Views of Computation in Computer Science
by more_original on Thursday September 01, 2016 @02:54AM
(#12403506)
No, I do mean formal machines like Turing Machines. Sequential composition of logarithmic space Turing Machines is a standard example for lack of compositionality.
If the simple parts are given by machines, then in general there is no canonical way of composing them into a machine for the composed program. You have to construct a new machine from the machines for the parts. An example is the sequential composition of two functions with logarithmic space usage. You cannot just use run one machine after the other, but you have to modify both machines and then build a new machine that contains them in the right way.
Of course, one may use systematic constructions to combine simple machines into more complicated ones. But this amounts to the implementation of a programming model.