3 ms·
What he means is that complicated programs can be built from simple parts. In programming languages you can just take simple parts and compose them into a singl
by more_original 10y ago
What he means is that complicated programs can be built from simple parts. In programming languages you can just take simple parts and compose them into a single program.
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.
- ankurdhama 10y agoI 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.
- more_original 10y agoNo, I do mean formal machines like Turing Machines. Sequential composition of logarithmic space Turing Machines is a standard example for lack of compositionality.