Sun Mon Tue Wed Thu Fri Sat
1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29 30 31
|
The Man Who Knew Too Much
I finished reading The Man Who Knew Too
Much, an biography of Alan Turing, by David Leavitt. I bought this book some years ago. The prime motivation to read it, is that I had
read that the movie The Imitation Game has some historical inaccuracies, and I wanted
to know these before I went to see the movie. My first remark is that editors
should consult a mathematician with respect to mathematical formuleas as the
book contains a number of inaccurately typeset mathematical formuleas. These
are some very basic formuleas: like using a double quote for the superscript
11, and using a subscript when a superscript should be used. This biography
suffers from the fact that there periods in the life of Turing where there
is not much known about him, that are filled with stories about other people,
event and such. The book also explains some of Turings papers in great
details. But these are almost unavoidable, and thus expected in such a
biography. I did have a problem with some of the suggestions that the author
made about how Turing could have experienced what happened in his life. I
found some of these too suggestive, as if the author wanted to tie together
everything in the life of Turing into a single process, as if that is even
possible in a normal life of a person.
Book sale
At bookshop Broekhuis they are having a sale
with 50% off for a large collection of books. I also looked at the large
collection of second hand books that they acquired. At 17:24:01, I bought
the book Logbook 1991-1992 by Harry Mulisch, ISBN:9789023428367, for
€ 9.45, which contains the diary of Harry Mulisch that he wrote
when working on his novel De ontdekking van de hemel (The
discovery of Heaven).
Snow
This morning, there fell about 6 cm (2.4 inch) of snow. In the afternoon, the sun started to shine and it the snow
started to melt.
Merging moves in trees
The kind of trees we are dealing with have a single root node and nodes are
placed in levels depending on their 'distance' from the root. It could also
be said that it is a tree with a parent-child relationship. (A concreet
example of this kind of tree is found in a directory structure with folders
and files, where both folders and files represent nodes in the tree, the
files being leave nodes.) When a single user is making changes to such a
tree by each time moving a single node to a new 'parent' where the parent
is not one of its own 'descendants', the tree will always remain a tree with
nodes placed in levels (possibly different level for some of the nodes each
time a node is moved). If a user would be allowed to move two nodes with the
above restriction, then it is possible to break the organization of the
tree, where it breaks in two part, with one part containing the root node and
still being proper and the other part being cyclic, where a chain of nodes
are all each owns descendants.
If two users in isolation move nodes around, such that the tree remains
well organized, it is not always possible to merge their changes without
the tree falling apart in two or more pieces. Of course, there is already
a problem when both users move the same node to a different parent. Combining
the moves of two users is similar to one user being allowed to make two moves
at the same time. The clasical example is tree, using the prefix with
children between brackets notation: A(B(C),D(E)), where one user moves D under
C, resulting in the tree A(B(C(D(E)))), and the other user moves B under E,
resulting in the tree A(D(E(B(C)))). When both moves are combined (merged),
this results in a lonely A node and an cycle consisting of B, C, D, and E.
There is no additional complexity in merging the moves of more than two users.
In case there is a problem with merging the results of more than two users,
there is always a minimal set of users whoes moves cannot be merged. Minimal
in the sense that there is no subset of this set which cannot be merged.
Because of this one could divide the users of the minimal set in two
(non-empty) groups that can be merged. Merging the combined moves of these
two groups is similar to the two user problem. It should be noted that it
is possible that a large group of user could be combined without problems.
Taking the above example, lets assume that there is a third user who moves
E to A resulting in the tree A(B(C),D,E). Combining the moves of these tree
users results in the tree A(E(B(C(D)))). There are good reasons to require
that the moves of a set of users can only merged if any subset (or at least
two users) can be merged into a proper tree. One reason being that if this
requirement is stated, the moves of the users can be pairwise merged in any
order.
The design of a locking mechanism to enforce that moves being made by a
group of users can always be merged in any possible order, is far from
trivial, especially if it needs to be efficient in time and space. There
is a whole range of fine-grained to coarse-grained locking mechanism. One
should take into the likelihood of multiple users applying moves to the
same part of the tree. It is useless to implement an expensive fine-grained
locking mechanism if the likelihood is low.
This months interesting links
Home
| December 2014
| February 2015