Ciro Santilli @cirosantilli 37

This section is about ways in which you can represent a tree.

Trees are a specific type of graph, so any graph representation also provides a way to represent a tree.

Therefore this section will focus only on methods specific to tress, and which cannot be used for graphs in general.

A Turing machine that simulates another Turing machine/input pair that has been encoded as a string.

In other words: an emulator!

The concept is fundamental to state several key results in computer science, notably the halting problem.

Subtle is the Lord by Abraham Pais (1982) chapter 4 "Entropy and Probability" mentions well how Boltzmann first thought that the second law was an actual base physical law of the universe while he was calculating numerical stuff for it, including as late as 1872.

But then he saw an argument by Johann Joseph Loschmidt that given the time reversibility of classical mechanics, and because they were thinking of atoms as classical balls as in the kinetic theory of gases, then there always exist a valid physical state where entropy decreases, by just reversing the direction of time and all particle speeds.

So from this he understood that the second law can only be probabilistic, and not a fundamental law of physics, which he published clearly in 1877.

As per en.wikipedia.org/w/index.php?title=Semidirect_product&oldid=1040813965#Properties, unlike the Direct product, the semidirect product of two goups is neither unique, nor does it always exist, and there is no known algorithmic way way to tell if one exists or not.

This is because reaching the "output" of the semidirect produt of two groups requires extra non-obvious information that might not exist. This is because the semi-direct product is based on the product of group subsets. So you start with two small and completely independent groups, and it is not obvious how to join them up, i.e. how to define the group operation of the product group that is compatible with that of the two smaller input groups. Contrast this with the Direct product, where the composition is simple: just use the group operation of each group on either side.

Product of group subsets

So in other words, it is not a function like the Direct product. The semidiret product is therefore more like a property of three groups.

The semidirect product is more general than the direct product of groups when thinking about the group extension problem, because with the direct product of groups, both subgroups of the larger group are necessarily also normal (trivial projection group homomorphism on either side), while for the semidirect product, only one of them does.

Conversely, en.wikipedia.org/w/index.php?title=Semidirect_product&oldid=1040813965 explains that if $G=N⋊H$, and besides the implied requirement that N is normal, H is also normal, then $G=N\times H$.

Smallest example: $D_6=C_3⋊C_2$ where $D$ is a dihedral group and $C$ are cyclic groups. $C_3$ (the rotation) is a normal subgroup of $D_6$, but $C_2$ (the flip) is not.

Note that with the Direct product instead we get $C_6$ and not $D_6$, i.e. $C_3\times C_2=C_6$ as per the direct product of two cyclic groups of coprime order is another cyclic group.

TODO:

Bibliography: math.stackexchange.com/questions/1726939/is-this-intuition-for-the-semidirect-product-of-groups-correct