## Freeman Dyson on Wittgenstein

October 21, 2012

[ source ]

Wittgenstein, unlike Heidegger, did not establish an ism. He wrote very little, and everything that he wrote was simple and clear. The only book that he published during his lifetime was Tractatus Logico-Philosophicus, written in Vienna in 1918 and published in England with a long introduction by Bertrand Russell in 1922. It fills less than two hundred small pages, even though the original German and the English translation are printed side by side. I was lucky to be given a copy of the Tractatus as a prize when I was in high school. I read it through in one night, in an ecstasy of adolescent enthusiasm. Most of it is about mathematical logic. Only the last five pages deal with human problems. The text is divided into numbered sections, each consisting of one or two sentences. For example, section 6.521 says: “The solution of the problem of life is seen in the vanishing of this problem. Is not this the reason why men, to whom after long doubting the sense of life became clear, could not then say wherein this sense consisted?” The most famous sentence in the book is the final section 7: “Wherof one cannot speak, thereof one must be silent.”

I found the book enlightening and liberating. It said that philosophy is simple and has limited scope. Philosophy is concerned with logic and the correct use of language. All speculations outside this limited area are mysticism. Section 6.522 says: “There is indeed the inexpressible. This shows itself. It is the mystical.” Since the mystical is inexpressible, there is nothing more to be said. Holt summarizes the difference between Heidegger and Wittgenstein in nine words: “Wittgenstein was brave and ascetic, Heidegger treacherous and vain.” These words apply equally to their characters as human beings and to their intellectual output.

Wittgenstein’s intellectual asceticism had a great influence on the philosophers of the English-speaking world. It narrowed the scope of philosophy by excluding ethics and aesthetics. At the same time, his personal asceticism enhanced his credibility. During World War II, he wanted to serve his adopted country in a practical way. Being too old for military service, he took a leave of absence from his academic position in Cambridge and served in a menial job, as a hospital orderly taking care of patients. When I arrived at Cambridge University in 1946, Wittgenstein had just returned from his six years of duty at the hospital. I held him in the highest respect and was delighted to find him living in a room above mine on the same staircase. I frequently met him walking up or down the stairs, but I was too shy to start a conversation. Several times I heard him muttering to himself: “I get stupider and stupider every day.”

Finally, toward the end of my time in Cambridge, I ventured to speak to him. I told him I had enjoyed reading the Tractatus, and I asked him whether he still held the same views that he had expressed twenty-eight years earlier. He remained silent for a long time and then said, “Which newspaper do you represent?” I told him I was a student and not a journalist, but he never answered my question.

Wittgenstein’s response to me was humiliating, and his response to female students who tried to attend his lectures was even worse. If a woman appeared in the audience, he would remain standing silent until she left the room. I decided that he was a charlatan using outrageous behavior to attract attention. I hated him for his rudeness. Fifty years later, walking through a churchyard on the outskirts of Cambridge on a sunny morning in winter, I came by chance upon his tombstone, a massive block of stone lightly covered with fresh snow. On the stone was written the single word, “WITTGENSTEIN.” To my surprise, I found that the old hatred was gone, replaced by a deeper understanding. He was at peace, and I was at peace too, in the white silence. He was no longer an ill-tempered charlatan. He was a tortured soul, the last survivor of a family with a tragic history, living a lonely life among strangers, trying until the end to express the inexpressible.

__________

Source:

Freeman Dyson, What can you really know?, The New York Review of Books, November 8, 2012.

## Deterministic Finite Automata in Haskell

October 2, 2012

Consider the deterministic finite automaton [1] illustrated below

[ state diagram courtesy of Michael Sipser [1] ]

Henceforth, we will call this automaton $M_1$. Note that $M_1$ has three states, labeled $q_1$, $q_2$, and $q_3$. The start state is $q_1$ (note the arrow coming from nowhere) and the accept state is $q_2$ (note the double circle). There are two possible inputs, labeled $0$ and $1$, and, depending on the input, the automaton will jump from one state to another. In the diagram above these state transitions are depicted using arrows connecting two states.

Suppose that the automaton $M_1$ receives an input string such as $1101$ (which the automaton reads from left to right). Since the start state is $q_1$ and the first input symbol is $1$, the automaton will jump to state $q_2$. The second input symbol is $1$, so the automaton will remain at $q_2$. The automaton reads the third input symbol, which is $0$, and then jumps from state $q_2$ to state $q_3$. The last input symbol is $1$ and thus the automaton jumps from state $q_3$ to state $q_2$. Hence, the state sequence corresponding to the input string $1101$ is the following

$q_1 \xrightarrow{1} q_2 \xrightarrow{1} q_2 \xrightarrow{0} q_3 \xrightarrow{1} q_2$

After reading the last symbol in the input string, $M_1$ produces an output. Since the final state $q_2$ is the accept state, we have that the automaton produces the output “accept”. Were the final state not $q_2$, the automaton would produce the output “reject”. We conclude that this automaton accepts the input string $1101$. What other input strings does $M_1$ accept? Michael Sipser answers this question in [1]:

Experimenting with this machine on a variety of input strings reveals that it accepts the strings $1$, $01$, $11$, and $0101010101$. In fact, $M_1$ accepts any string that ends with a $1$, as it goes to its accept state $q_2$ whenever it reads the symbol $1$. In addition, it accepts strings $100$, $0100$, $110000$, and $0101000000$, and any string that ends with an even number of $0$s following the last $1$. It rejects other strings, such as $0$, $10$, $101000$.

A set of strings is called a language [1]. The set of all input strings accepted by the deterministic finite automaton $M_1$ is a language which we denote by $L (M_1)$.

__________

Formal definition

A deterministic finite automaton (DFA) consists of a finite set of states $Q$, a finite input alphabet $\Sigma$ that tells us what the allowed input symbols are, a transition function $\delta : Q \times \Sigma \to Q$ that tells us how to jump from one state to another, a start state $q_0 \in Q$, and a set of accept states $A \subseteq Q$. A deterministic finite automaton (DFA) is thus a $5$-tuple of the form

$(Q, \Sigma, \delta, q_0, A)$

The deterministic finite automaton $M_1$ which we discussed earlier in this post is defined formally as follows

$M_1 := (\{q_1, q_2, q_3\}, \{0,1\}, \delta, q_1, \{q_2\})$

where the transition function $\delta: \{q_1, q_2, q_3\} \times \{0,1\} \to \{q_1, q_2, q_3\}$ is defined enumeratively as

$\delta (q_1, 0) = q_1$,        $\delta (q_2, 0) = q_3$,        $\delta (q_3, 0) = q_2$

$\delta (q_1, 1) = q_2$,        $\delta (q_2, 1) = q_2$,        $\delta (q_3, 1) = q_2$

Alternatively, we could view each state transition $q_i \xrightarrow{\sigma} q_j$ as an ordered triple $(q_i, \sigma, q_j)$, which might be easier to implement in some programming languages.

__________

Computing state sequences

Given an input string $\sigma = \sigma_1 \sigma_2 \dots \sigma_n$ over a given alphabet $\Sigma$, how do we obtain the corresponding state sequence? I solved that problem last January. I will not repeat myself here, but the crux of the matter is that the final state can be obtained using a left-fold

$\text{foldl} \, \delta \, q_0\, [\sigma_1, \sigma_2, \dots, \sigma_{n}]$

whereas the entire state sequence can be computed using a left-scan

$\text{scanl} \, \delta \, q_0\, [\sigma_1, \sigma_2, \dots, \sigma_{n}]$

Lacking a better name, I called this procedure the “scanl trick“, as I used the Haskell function scanl to implement it. Please let me know if you find a more sophisticated name for this “trick”.

__________

Haskell implementation of the DFA

Without further ado, here is a Haskell script:

data State = Q1 | Q2 | Q3 deriving (Read, Show, Eq)

type Input = Integer

-- define state-transition function
delta :: State -> Input -> State
delta Q1 0 = Q1
delta Q1 1 = Q2
delta Q2 0 = Q3
delta Q2 1 = Q2
delta Q3 0 = Q2
delta Q3 1 = Q2
delta  _ _ = error "Invalid input!"

-- define initial state
initialstate :: State
initialstate = Q1

-- create list of accept states
acceptstates :: [State]
acceptstates = [Q2]

-- create infinite list of input sequences
inputss :: [[Input]]
inputss = concat $iterate g [[]] where g = concat . map (\xs -> [ xs ++ [s] | s <- [0,1]]) -- create accept predicate isAccepted :: [Input] -> Bool isAccepted inputs = finalstate elem acceptstates where finalstate = foldl delta initialstate inputs -- compute language recognized by the DFA language :: [[Input]] language = filter isAccepted inputss Some remarks about this script are in order. Please note that: • Sets are represented by lists. Strings are represented by lists, too. The latter is more natural than the former. Sets of strings become lists of lists. • A new data type is created to represent the states, which we denote by Q1, Q2, and Q3. The input symbols are integers. • Note that Input is a type synonym, inputs is a list of inputs symbols (i.e., an input string), and inputss is a list of lists of inputs (i.e., a list of input strings). Yes, it is a bit confusing. • The final state is computed using the higher-order function foldl (left-fold). We check if the final state is an accept state using the list membership predicate elem. If you have any objections to this script, please do let me know. Let us now test it! We load it into GHCi and voilà: *Main> -- check list of input strings *Main> take 31$ inputss
[[],[0],[1],
[0,0],[0,1],[1,0],[1,1],
[0,0,0],[0,0,1],[0,1,0],[0,1,1],
[1,0,0],[1,0,1],[1,1,0],[1,1,1],
[0,0,0,0],[0,0,0,1],[0,0,1,0],[0,0,1,1],
[0,1,0,0],[0,1,0,1],[0,1,1,0],[0,1,1,1],
[1,0,0,0],[1,0,0,1],[1,0,1,0],[1,0,1,1],
[1,1,0,0],[1,1,0,1],[1,1,1,0],[1,1,1,1]]
*Main> -- compute the language of the automaton
*Main> -- (let us extract some 40 input strings only)
*Main> take 40 language
[[1],[0,1],[1,1],
[0,0,1],[0,1,1],[1,0,0],[1,0,1],[1,1,1],
[0,0,0,1],[0,0,1,1],[0,1,0,0],[0,1,0,1],
[0,1,1,1],[1,0,0,1],[1,0,1,1],[1,1,0,0],
[1,1,0,1],[1,1,1,1],[0,0,0,0,1],[0,0,0,1,1],
[0,0,1,0,0],[0,0,1,0,1],[0,0,1,1,1],[0,1,0,0,1],
[0,1,0,1,1],[0,1,1,0,0],[0,1,1,0,1],[0,1,1,1,1],
[1,0,0,0,0],[1,0,0,0,1],[1,0,0,1,1],[1,0,1,0,0],
[1,0,1,0,1],[1,0,1,1,1],[1,1,0,0,1],[1,1,0,1,1],
[1,1,1,0,0],[1,1,1,0,1],[1,1,1,1,1],[0,0,0,0,0,1]]

The list of input strings is exactly the same I posted yesterday. The input strings in the language $L (M_1)$, or, to put it more precisely, the input strings in $L (M_1)$ that are displayed above either end with a $1$, or end “with an even number of $0$s following the last $1$“, as mentioned by Sipser in [1]. Why is that? The last $1$ in the input string puts $M_1$ in state $q_2$, and an even number of $0$s after that $1$ lead to transitions from $q_2$ to $q_3$ and back to $q_2$, e.g.,

$q_2 \xrightarrow{0} q_3 \xrightarrow{0} q_2$

or

$q_2 \xrightarrow{0} q_3 \xrightarrow{0} q_2 \xrightarrow{0} q_3 \xrightarrow{0} q_2$

or

$q_2 \xrightarrow{0} q_3 \xrightarrow{0} q_2 \xrightarrow{0} q_3 \xrightarrow{0} q_2 \xrightarrow{0} q_3 \xrightarrow{0} q_2 \xrightarrow{0} q_3 \xrightarrow{0} q_2$

It would also be interesting to take a look at the state sequences corresponding to the input strings in $L(M_1)$. We compute these state sequences using the infamous “scanl trick“:

*Main> -- create list of sequences of states
*Main> let statess = map (\xs -> scanl delta initialstate xs) language
*Main> -- take the "first" 20 state sequences
*Main> take 20 statess
[[Q1,Q2],[Q1,Q1,Q2],[Q1,Q2,Q2],
[Q1,Q1,Q1,Q2],[Q1,Q1,Q2,Q2],[Q1,Q2,Q3,Q2],
[Q1,Q2,Q3,Q2],[Q1,Q2,Q2,Q2],[Q1,Q1,Q1,Q1,Q2],
[Q1,Q1,Q1,Q2,Q2],[Q1,Q1,Q2,Q3,Q2],[Q1,Q1,Q2,Q3,Q2],
[Q1,Q1,Q2,Q2,Q2],[Q1,Q2,Q3,Q2,Q2],[Q1,Q2,Q3,Q2,Q2],
[Q1,Q2,Q2,Q3,Q2],[Q1,Q2,Q2,Q3,Q2],[Q1,Q2,Q2,Q2,Q2],
[Q1,Q1,Q1,Q1,Q1,Q2],[Q1,Q1,Q1,Q1,Q2,Q2]]

Note that all state trajectories end in state Q2, as we expected.

__________

References

[1] Michael Sipser, Introduction to the Theory of Computation (2nd edition), Thomson Course Technology, 2006.

## Generating all words over an alphabet

October 1, 2012

An alphabet $\Sigma$ is a finite set of symbols. A word $w$ of length $n$ over an alphabet $\Sigma$ is a sequence of symbols from $\Sigma$, i.e.,

$w : \{0,1,\dots,n-1\} \to \Sigma$

Alternatively, we can view a word $w$ of length $n$ over the alphabet $\Sigma$ as an $n$-tuple (i.e., an ordered list with $n$ elements) over $\Sigma$, i.e., $w \in \Sigma^n$. The set of all finite words over $\Sigma$, including the empty word $\varepsilon$, is denoted by $\Sigma^*$, where $*$ is the Kleene star.

We thus encounter the following problem:

Problem: Given an alphabet $\Sigma$, how do we generate all the words over $\Sigma$? In other words, given $\Sigma$, how do we generate the Kleene closure $\Sigma^*$?

The following Haskell script solves this problem:

g :: [a] -> [[a]] -> [[a]]
g alphabet = concat . map (\xs -> [ xs ++ [s] | s <- alphabet])

allwords :: [a] -> [[a]]
allwords alphabet = concat $iterate (g alphabet) [[]] where alphabet must be a finite list, otherwise the execution of the script won’t ever terminate. The script above, although short, uses a lot of machinery: list comprehension, higher-order functions map and iterate, concatenation of lists of lists, and partial function application. Let us test this script. First, we load it into GHCi. Then we can run a GHCi session: *Main> -- define alphabet *Main> let alphabet = [0,1] *Main> -- define function f *Main> let f = g alphabet *Main> -- check type *Main> :t f f :: [[Integer]] -> [[Integer]] *Main> -- apply f to several lists of lists *Main> f [[]] [[0],[1]] *Main> (f . f) [[]] [[0,0],[0,1],[1,0],[1,1]] *Main> (f . f . f) [[]] [[0,0,0],[0,0,1],[0,1,0],[0,1,1],[1,0,0],[1,0,1],[1,1,0],[1,1,1]] So far, so good. Suppose that we would like to find all words over alphabet $\Sigma_2 := \{0,1\}$ whose length is less than or equal to $4$. How many such words are there? There are $|\Sigma_2|^k = 2^k$ words of length $k$. Hence, there are $\displaystyle\sum_{k=0}^n 2^k = \frac{2^{n+1} -1}{2-1} = 2^{n+1} - 1$ binary words of length less than or equal to $n$. Hence, if we make $n = 4$, then we obtain $2^{n+1}-1 = 31$. Continuing our GHCi session: *Main> take 31$ allwords alphabet
[[],[0],[1],
[0,0],[0,1],[1,0],[1,1],
[0,0,0],[0,0,1],[0,1,0],[0,1,1],
[1,0,0],[1,0,1],[1,1,0],[1,1,1],
[0,0,0,0],[0,0,0,1],[0,0,1,0],[0,0,1,1],
[0,1,0,0],[0,1,0,1],[0,1,1,0],[0,1,1,1],
[1,0,0,0],[1,0,0,1],[1,0,1,0],[1,0,1,1],
[1,1,0,0],[1,1,0,1],[1,1,1,0],[1,1,1,1]]

Very nice! We could use this in Coding Theory! For example, suppose that we would like to find all binary words of length $8$ whose Hamming weight is equal to $5$. There are

$\displaystyle\binom{8}{5} = \frac{8!}{3! 5!} = 56$

such words. We can find them as follows:

*Main> -- take all words of length less than or equal to 8
*Main>  let words = take 511 \$ allwords alphabet
*Main> -- filter out binary words of length 8
*Main> let wordsL8 = filter (\xs -> length xs == 8) words
*Main> length wordsL8
256
*Main> -- filter out binary words of length 8
*Main> -- and also of Hamming weight equal to 5
*Main> let wordsL8H5 = filter (\xs -> sum xs == 5) wordsL8
*Main> length wordsL8H5
56
*Main> wordsL8H5
[[0,0,0,1,1,1,1,1],[0,0,1,0,1,1,1,1],[0,0,1,1,0,1,1,1],
[0,0,1,1,1,0,1,1],[0,0,1,1,1,1,0,1],[0,0,1,1,1,1,1,0],
[0,1,0,0,1,1,1,1],[0,1,0,1,0,1,1,1],[0,1,0,1,1,0,1,1],
[0,1,0,1,1,1,0,1],[0,1,0,1,1,1,1,0],[0,1,1,0,0,1,1,1],
[0,1,1,0,1,0,1,1],[0,1,1,0,1,1,0,1],[0,1,1,0,1,1,1,0],
[0,1,1,1,0,0,1,1],[0,1,1,1,0,1,0,1],[0,1,1,1,0,1,1,0],
[0,1,1,1,1,0,0,1],[0,1,1,1,1,0,1,0],[0,1,1,1,1,1,0,0],
[1,0,0,0,1,1,1,1],[1,0,0,1,0,1,1,1],[1,0,0,1,1,0,1,1],
[1,0,0,1,1,1,0,1],[1,0,0,1,1,1,1,0],[1,0,1,0,0,1,1,1],
[1,0,1,0,1,0,1,1],[1,0,1,0,1,1,0,1],[1,0,1,0,1,1,1,0],
[1,0,1,1,0,0,1,1],[1,0,1,1,0,1,0,1],[1,0,1,1,0,1,1,0],
[1,0,1,1,1,0,0,1],[1,0,1,1,1,0,1,0],[1,0,1,1,1,1,0,0],
[1,1,0,0,0,1,1,1],[1,1,0,0,1,0,1,1],[1,1,0,0,1,1,0,1],
[1,1,0,0,1,1,1,0],[1,1,0,1,0,0,1,1],[1,1,0,1,0,1,0,1],
[1,1,0,1,0,1,1,0],[1,1,0,1,1,0,0,1],[1,1,0,1,1,0,1,0],
[1,1,0,1,1,1,0,0],[1,1,1,0,0,0,1,1],[1,1,1,0,0,1,0,1],
[1,1,1,0,0,1,1,0],[1,1,1,0,1,0,0,1],[1,1,1,0,1,0,1,0],
[1,1,1,0,1,1,0,0],[1,1,1,1,0,0,0,1],[1,1,1,1,0,0,1,0],
[1,1,1,1,0,1,0,0],[1,1,1,1,1,0,0,0]]

where we used function take (again) and higher-order function filter. The two predicates were built using anonymous functions.

I am happy with this script. Please let me know in case you are not.

__________

Related:

## Gell-Mann on learning

September 27, 2012

Murray Gell-Mann on why being in awe inhibits learning:

I said I’d rather be poor or die than be an engineer because I would be no good at it. If I designed something it would fall down. When I was admitted to Yale, I took an aptitude test, and when the counselor gave me the results of the exam, he said: “You could be lots of different things. But don’t be an engineer.”

After my father gave up on engineering, he said, ‘How about we compromise and go with physics? General relativity, quantum mechanics, you will love it.’ I thought I would give my father’s advice a try. I don’t know why. I never took his advice on anything else. He told me how beautiful physics would be if I stuck with it, and that notion of beauty impressed me. My father studied those things. He was a great admirer of Einstein. He would lock himself in his room and study general relativity. He never really understood it. My opinion is that you have to despise something like that to get good at it.

If you admire it sufficiently, you’ll be in awe of it, so you’ll never learn it. My father thought it must be very hard, and it will take years to understand it, and only a few people understand it, and so on. But I had a wonderful teacher at Yale, Henry Margenau, who took the opposite attitude. He thought relativity was for everybody. Just learn the math. He’d say, “We’ll prepare the math on Tuesday and Thursday, and we’ll cover general relativity on Saturday and next Tuesday.” And he was right. It isn’t that bad.

__________

Source:

Susan Kruglinski, The Man Who Found Quarks and Made Sense of the Universe, DISCOVER Magazine, April 2009.

## My implementation of (!!)

September 20, 2012

In Haskell we can easily create a list and then access its elements using the (!!) function, which is defined in the Prelude. Here is a very brief GHCi session:

Prelude> let xs = [7,8,9]
Prelude> xs !! 0
7
Prelude> xs !! 1
8
Prelude> xs !! 2
9

So far, so good. What if the index is negative or equals / exceeds the list’s length? Let’s see what happens in those cases:

Prelude> xs !! (-1)
*** Exception: Prelude.(!!): negative index

Prelude> xs !! 3
*** Exception: Prelude.(!!): index too large

As expected, we get error messages. What if we used the Maybe data type to avoid exceptions? This is exercise 4 in chapter 3 of O’Donnell & Hall & Page [1], which is phrased as follows:

Write (!!), a function that takes a natural number $n$ and a list and selects the $n$th element of the list. List elements are indexed from $0$, not $1$, and since the type of the incoming number does not prevent it from being out of range, the result should be a Maybe type.

The aforementioned authors propose the following implementation:

import Prelude hiding ((!!))

(!!) :: Int -> [a] -> Maybe a
(!!) n [] = Nothing
(!!) 0 (x:xs) = Just x
(!!) n (x:xs) = (!!) (n-1) xs

where I added the import line to hide the standard (!!) function that is defined in the Prelude. My first thought was that the authors switched the function arguments, which makes the function look silly. Let’s give it a try. Here’s another GHCi session:

*Main> let xs = [7,8,9]
*Main> 0 !! xs
Just 7
*Main> 1 !! xs
Just 8
*Main> 2 !! xs
Just 9
*Main> (-1) !! xs
Nothing
*Main> 3 !! xs
Nothing

It appears to be working, but specifying the index before the list looks rather ugly. Wait, what if the index is negative? For example, why does (-3) !! xs return Nothing? Let’s use equational reasoning to find out:

(-3) !! [7,8,9] = (-4) !! [8,9] =
= (-5) !! [9] =
= (-6) !! [] =
= Nothing

This reveals a fatal flaw in the authors’ implementation: if the list is infinite, then the recursion will never terminate. For example, (-1) !! [0..] will never terminate, because when the initial index is negative, decrementing the index will never get us to the zero index.

Therefore, I propose the following implementation:

import Prelude hiding ((!!))

(!!) :: [a] -> Integer -> Maybe a
(!!)     [] n = Nothing
(!!) (x:xs) n | n > 0  = (!!) xs (n-1)
| n == 0 = Just x
| n < 0  = Nothing

where the first argument is now a list, and the second argument an integer. Note that I used indices of type Integer (“mathematical integers”), instead of type Int (“computer integers”). Let’s see if this implementation works:

*Main> let xs = [7,8,9]
*Main> xs !! 0
Just 7
*Main> xs !! 1
Just 8
*Main> xs !! 2
Just 9
*Main> xs !! (-1)
Nothing
*Main> xs !! 3
Nothing

It appears to be working. No errors. No exceptions. If you, dear reader, happen to be acquainted with Haskell you will almost certainly be shocked (!!!), for this function is trivial! Well, that is true, but I allow myself to be intrigued by trivialities. Moreover, this function is simple enough to allow us to use equational reasoning. For example, let’s compute xs !! 2 using equational reasoning:

[7,8,9] !! 2 = [8,9] !! 1 = [9] !! 0 = Just 9

What if the index is too large? Let’s compute xs !! 4 then:

[7,8,9] !! 4 = [8,9] !! 3 = [9] !! 2 = [] !! 1 = Nothing

Step by step, by successively removing the head of the list, we get where we want to. Unfortunately, this suggests that accessing an arbitrary element of the list will not be $\mathcal{O} (1)$.

__________

References

[1] John O’Donnell, Cordelia Hall, Rex Page, Discrete Mathematics using a Computer (2nd edition), Springer, 2006.