A set of computations that, composed with one another, permit one to recover the whole set of possible computations in the repertoire of the universal computer is called a ‘universal set’. When there is a universal set, any computation is reducible to a sequence of elementary computations selected from the universal set.
DOT FROM two-level-diagram
These elementary computations are, in this respect, a bit like LEGO bricks: anything that is allowed in a LEGO world (from cars, to villas, to pirate ships) can be decomposed into elementary LEGO bricks of a few elementary different kinds, whose basic composition rules are fixed.
Likewise, when there is a universal set, any physically allowed computation can be decomposed into a set of elementary computations from the universal set, sometimes referred to as ‘Gates’, which can be composed according to fixed laws.
When the laws of physics say that a universal set of computations is possible, we say that they display ‘universality’. Universality is a counterfactual property (about what is possible), and it has sweeping consequences: it is universality that permits the existence of a universal computer, like the ones we use nowadays.
This property was first grasped in the Victorian era. At that time, the inventor Charles Babbage proposed a scheme to build what he called the Analytical Engine. This would have been, if realised, the first programmable computer – the ancestor of our modern ones, only far larger and made of brass mechanical cogs and wheels. Ada Lovelace, Babbage’s collaborator and a brilliant mathematician, understood the universality of this machine, conjecturing in her notes that the Analytical Engine could be used to produce all sorts of […]
~
MARLETTO, Chiara, 2021. The science of can and can’t: a physicist’s journey through the land of counterfactuals. New York: Viking. ISBN 978-0-525-52193-8, p. 92.
We often point to Lady Ada as the world's first programmer. But what did she program? And why is it important?
Ward gave a TED talk in Oregon about how he invented wiki. He reached the end of web, instead of stopping, decided to add a button to keep going. Hence wiki was born and later forked creating Wikipedia.