-
Excerpts from Leslie Lamport’s Interviews
Sources:
A Discussion with Leslie Lamport
An Interview with Leslie Lamport
1. When asked about some of the important problems in distributed systems.
On the theory side, recognizing a problem has been harder than solving it. Since you are asking about problems that are already recognized to be problems, the answer is probably none. On the practical side, I don’t think I have any more insight into that than most other people.
2. When asked about currently available formal methods are unable to prove correctness of large software systems, such as real operating systems. What is your advice to software developers for bridging this gap between algorithms (which can be analyzed) and full software systems?
People fiercely resist any effort to make them change what they do. Given how bad they are at writing programs, one might naively expect programmers to be eager to try new approaches. But human psychology doesn’t work that way, and instead programmers will find any excuse to dismiss an approach that would require them to learn something new. On the other hand, they are quick to embrace the latest fad (extreme programming, templates, etc.) that requires only superficial changes and allows them to continue doing things basically the same as before. In this context, it is only fair to mention that people working in the area of verification are no less human than programmers, and they also are very reluctant to change what they do just because it isn’t working.
3. The fundamental idea behind verification is that one should think about what a program is supposed to do before writing it. Thinking is a difficult process that requires a lot of effort. Write a book based on a selection of distorted anecdotes showing that instincts are superior to rational judgment and you get a best seller. Imagine how popular a book would be that urged people to engage in difficult study to develop their ability to think so they could rid themselves of the irrational and often destructive beliefs they now cherish. So, trying to get people to think is dangerous. Over the centuries, many have been killed in the attempt.
4. I think my most important contribution is my work on writing structured proofs, which is perhaps more relevant to mathematicians than computer scientists. In the unlikely event that I’m remembered 100 years from now, I expect it will be for that.
-
Ordered Pairs in Naive Set Theory
Ordered Pair
An ordered pair of a and b, with first co-ordinate a and second co-ordinate b is defined by,
(a,b) = {{a}, {a,b}}
The proof for the above ordered pair is given by,
If (a,b) and (x,y) are two ordered pairs, then (a,b) = (x,y) if and only if a=x and b=y.
Proof:
If in case, a = b, then, (a,b) => the singleton set of {{a}} or the singleton set of {{b}}.
Also, conversely, if (a,b) itself is a singleton set, results in {a} = {a,b}, so {b} ϵ {a,b} so which leads to a=b
On the other hand if we assume , (a,b) = (x,y) then both of them have to be singletons which can lead to
Singletons on both the sides, like {a} = {x}, so that a = x.
Also both the pairs should have atleast have one element which is not a singleton({a,b} and {x,y}), it results to {a,b} ={x,y}.
Now since we already know that b ϵ {a,b}, b is also a subset of {x,y}.
Since a=x, b also cannot be equal to x and hence, b = y.
T his completes the proof that, (a,b) = (x,y) If and only if a=x and b=y.
Cartesian product:
When A and B are two sets, we can define a set which contains the ordered pair (a,b) such that a is in A and b is in B.
Assuming above, we can conclude that {a} ϲ A and {b} c B, implies that {a,b} c A U B. Also, {a} C (A U B) and {b} C {AUB}, which implies, (a,b) C {A U B}.
There is an important observation from this, {a}, {b}, {a,b} are actually some of the members of the power set of the elements of the set {a,b}. So we can conclude that, (a,b) ϵ ‽(a,b). Its also obvious that ‽(a,b) has more elements than the ordered pair hence we can define a new set ‽(‽(a,b)) when a ϵ A and b ϵ B.
Applying the axiom of specification and axiom of extension we can obtain the set A X B which is the Cartesian product such that
A X B = {x:x=(a,b) for some a in A and some b in B}.
We can take forward the equation in a converse order for any set of ordered pairs there exists a set R such that, for sets A and B, R C (A X B).
Now, ({a},{a,b}) ϵ U R. Now, since {a,b} is one of the subsets of the ordered pair, its safe to assume that, {a,b} ϵ U R. This also assumes that a and b also belongs to UUR.
Projections
Its also often desirable to construct projections (like projection in relation algebra for example). By using the definitions,
A = { a: for some b in ((a,b) ϵ R)}
B = { b: for some a in ((a,b) ϵ R)}
-
Compliments in Set Theory
Relative Difference
If A and B are two sets, then the difference between A and B, the relative compliment of B in A, is the set A - B defined by (note that = is just a abuse that
we use to ϵ)
A − B = xϵA : xϵ′ B
This does not necessarily mean B ⊂ A
But when the above condition holds true, then
A − B = A − (A ∩ B)
For the sake of simplicity, we assume a set U , the universe on which we can assume that all sets that we create are subsets of them.
Given a set A, we can define a set which is the absolute compliment of A, which is A’, which also provides that (A’)’ = A.
Also as with all ∅,
∅’ = E and E’ = ∅
Also, its easy to prove that,
A ∩ A′ = ∅
Also,
A ⊂ B if andonlyif , B′ ⊂ A′Lets proceed to prove the above one. Lets assume the if part, if B′ ⊂ A′ : if xϵA, its self evident that xϵ′ A, and since B′ ⊂ A′ which clearly implies that , x ⊂ B′ which leaves us withxϵAandxϵB. Proceeding with the only if part, A ⊂ B if xϵB′ the clearly, xϵ′ B and since AϵB, its self evident that xϵ′ A, which proves the above one.
Moving forward with the De Morgans Laws,
(A ∪ B)′ = (A′ ∩ B′ )
Lets proceed to prove the above , lets assume xϵ left side then xϵ′ (A ∪ B) which
means, xϵ′ A and xϵ′ B which directly leads to xϵA and xϵB. Proceeding to the
right side, if xϵrightside then xϵ′ A and xϵ′ B which means that x is not present in
either A or B which leads to x being in A or B, hence, (A∪ B)′ = (A′ ∩ B′ ).Hence, Demorgan Law have been proved. Similiarly, we can also prove that
(A ∩ B)′ = A′ ∩ B′
Principle of duality of Sets
One of the major implication of De morgans law is that, all theorems in Set
theory come in pairs.
So if an inclusion or an equation containing, unions, intersections and compli-
ments of a sub-set E, we replace al l the sub-sets by its compliments, inverse its
unions and intersections and reverse the inclusion , we arrive at a new theorem.Symettric Difference
A + B = (A − B) ∪ (B − A)
This is the kin of XOR operation http : //en.wikipedia.org/wiki/Exclusivedisjunction
This is commutative and associative.
Why is theory of intersections only applicable to non ∅ sets ?
Lets just assume a set, where xϵX : xϵof ∅
Lets try to prove the other part, If this does not hold true, then ∅ must contain
a set X such that xϵX ′ , which of course is ridiculous, which proves the point.
To clear this, we can define a sub set in the Universe U, such that, ϱ(All subsets
of universe)
xϵU |xϵX f oreveryX inϱ -
Asymptotic Notations
Why use Asymptotic analysis?
Since its a well known fact that for a small input set, all algorithms perform well regardless of the complexity, so to determine the complexity we need to analyze the algorithm for large values of n , typically n -> infinity. Also we need to bound the computed value between two values(a range) , or in short create a subset within which the execution time of the algorithm falls.
An asymptote of the curve is a line such that the distance between the curve and the line approaches zero as they tend to infinity. So, we use this to determine the function which is fixed while n-> infinity.
Asymptotic notations are calculated based on if the asymptotic lower and upper bounds can be calculated for a function properly.
Various Notations
Θ - when both asymptotic upper and lower bounds can be calculated and is tight.
θ - when only asymptotic upper bound can be calculated and is tight.
Ω - when only asymptotic lower bound can be calculated and is tight.
o - when the asymptotic upper bound can be calculated but cannot be tight.
ω -Only when the asymptotic lower bound can be calculated but cannot be tight.
Θ Notation:
For functions g(n) and f(n), we define a function, Θ(g(n)) such that,
Θ(g(n)) ϵ { f(n): c1,c2,n0, all non-negative constants for, 0 ≤ c1g(n) ≤ f(n) ≤ c2g(n)}
What it essentially means is that, by using the above description, we obtain a set of f(n)’s where f(n) lies between the upper and lower bounds, effectively sandwiching f(n) within c1g(n) and c2g(n).
So, we obtain a set f(n) ϵ Θ(n), for sake of convenience we use the notation, f(n) = Θ(n).
This makes, g(n) asymtotically tight bound for f(n) meaning that f(n) is equal to g(n) within a given constant factor C0.
Assumptions:
∀ f(n) ϵ Θ(n), f(n) has to be asymptotically nonnegative for sufficiently large values of n.
Also, it requires g(n) to be asymptotically nonnegative as otherwise, Θ(g(n)) = ∅
So we reach a point where, any function computed with Θ(n) has to be asymptotically nonnegative.
When computing Θ(n), lower-order terms of a function can be ignored when computing the Θ(n) as its insignificant for large values of n.
Similiarly, to compute the value of the constants c1 and c2 which define the bounds of the function, its enough if we pick a lower bound value lesser than the higher-order term and upper bound greater than the higher-order term.
For any asymptotically nonnegative function with a higher-order term 0 or if its constant we use , Θ(n0) = Θ(1). (though its sure that 1-> infinity). This notation is just used to make clarity that the function computes in constant amount of time.
θ notation:
When we have only an fixed asymptotic upper bound, we use θ(g(n)) (pronounce as big oh.)
For functions f(n) and g(n), we define a function θ(g(n)) such that,
θ(g(n)) ε {f(n), for constants , c and n0, such that 0 ≤ f(n) ≤ c.g(n) ∀ n ≥ n0}
θ(g(n)) is a subset of θ(g(n)), if it exists as Θ notation is stronger than θ notation.
-> is most commonly used as asymptotic upper bound characterizes the worst-case behavior of an algorithm.
-> we arrive at an θ notation by looking at the structure of a program
What we mean by saying a program is θ(n2) what we mean is for any value of n, above a specified n0, running time is bounded above the value of the function f(n).
Ω notation:
When we have only an fixed asymptotic lower bound, we use Ω(g(n)) (pronounced as big omega.)
For functions f(n) and g(n), we define a function Ω(g(n)) such that,
Ω(g(n)) ε {f(n), for constants, c and no, such that 0 c.g(n) ≤ f(n) for all n < n0 }Following figure gives a clear understanding of the above notations:
Theorem 1:
For functions f(n) and g(n), f(n) ε Θ(g(n)) if and only if f(n) ε θ(g(n)) and f(n) ε Ω(g(n)).
o notation:
The asymptotic upper bound provided by \theta notation may or may not be tight. For ex, 2n ε θ(n2) is not tightly bound. In such cases we use little-oh of g(n)
For functions f(n) and g(n), we define a function o(g(n)) such that,
o(g(n)) ε {f(n), for constants c and n0, 0 ≤ f(n) ≤ c.g(n) for n>n0 and n0 a constant greater than 0}
ω notation:
When we have have an asymptotic lower bound provided by ω notation may or may not be tight.
In such case,
For functions f(n) and g(n), we define a function ω(g(n)) such that,
ω(g(n)) = { f(n), for constants, c and n0, 0 ≤ c.g(n) ≤ f(n)} -
Ignite talk on Cloning Einstein
Recently, i gave a talk in Ignite Chennai. The idea of Ignite is , if you are given 5 minutes and just 20 slides, What would you say? The idea is to present ideas concisely and briefly and ignite thoughts in the minds of listeners. In Chennai, this is the first ignite that is held and was conducted by Thoughtworks, the company where i currently work on. This is article is derived from the talk that i gave there.
Just to arouse the curiosity of the listeners, i decided to name it as “How would it be to clone Einstein”. In-fact, When people talk about cloning, what immediately flashes in human brain is cloning an individual. After all, even Time magazine has run more than 3 covers advertising the same conception. The irony is thescience of cloning is not just creating an identical copy of human beings, but a lot more.
Cloning can be broadly classified into two groups, Reproductive Cloning and Therapeutical Cloning. Reproductive cloning is concerned more about creating identical copies of an organism and this is the most common type of cloning that we hear in news, like Dolly the Sheep and the Interp. Ibex. The less known type of cloning is Therapeutical Cloning which has a lot of tricks up the sleeve that can increase the longevity of an individual.
Reproductive Cloning is a very imperfect science(link to xkcd comic) and it might take many generations to reach perfection. Instead, what Therapeutical Cloning concerns itself is with whatever we have in hand, how can we put it to benefit of the human society. Stem cell research is one such branch of cloning which concerns itself on organ replacement.
When a tree’s branch is cut down, The tree has a unique ability to grow the same kind of part, in this case leaves to serve the same function(photosynthesis). Given that a plant can re-create a cut down part by creating a re-placement to satisfy the function is something the ‘things’ in animal kingdom(i mean most of them, there are some animals which grow after a part is cut) lack. Stem cell research tries to get a solution for this. In this case, it just does not limit itself to external visible parts such as hands or legs.
Stem Cell Research attempts to fix this gap by using highly replicable cells such as the embryonic cells and cells from bone marrow. This is a lot different as we create only parts of the human body to aid the longevity. For example, a person with a defective heart or blood cancer could use the help of Stem Cells to heal the heart or blood cancer. Its a elixir which could save the life of countless ailing people, only that this time its from scientists and not from monks.
Recent Statistics point out that there are more than 153,000 deaths every day and the global life expectancy is put at 70 years around the globe. But not all who people die are 70 years old. Coupled to this is the fact that average life expectancy is decreasing owing to our increasingly bad lifestyle. Of course, Stem cell research will not solve all the healthcare problems that face us, but could at-least help someway or the other.
