ACL 2012

What’s interesting?

A Deep Learning Tutorial by Richard Socher, Yoshua Bengio and Chris Manning.

– Selective Sharing for Multilingual Dependency Parsing. I always like the work from MIT people. This is an interesting paper on multilingual learning. The model does not assume the existing of parallel corpus, which makes it more practical. Moreover, it can transfer linguistic structures between unrelated languages.

– Unsupervised Morphology Rivals Supervised Morphology for Arabic MT. Very close to my thesis. In fact, I just need to read Mark Johnson’s 2009 paper Improving nonparameteric Bayesian inference: experiments on unsupervised word segmentation with adaptor grammars.


One does not simply study Computational Complexity

Last night, I ran into an interesting question on Complexity while surfing the Internet. Here it is:

Let A be the language containing only the single string w where: w = 0 if God does exist and w = 1 otherwise. Is A decidable? Why or why not? (Note: the answer does not depend on your religious convictions.)

So what’s the proof. I come up with my proof that A is undecidable.

Consider a Turing Machine M used to decide A. If A is decidable, the Turing Machine M will stop and output God, the supreme being, in the output tape.

Forget about religious viewpoint, from logical point of view, let’s assume that God is the supreme being, who holds the most super power and can create anything. So, where does God come from? There must be another supreme being, who created God. The Turing Machine M, therefore continues working to output The One, who created God. But then, who created The One? Turing Machine M definitely enters infinite loop seeking for the original supreme being. Thus, A is undecidable.

Hey, does the proof sound familiar? Of course,  it’s an analogue version of Turtles all the way down. In case you’ve never heard of this philosophical story, here is one of those version, found in the first page of my book Plato and a Platypus Walk into a Bar, Philogagging chapter.

Dimitri: If Atlas holds up the world, what holds up Atlas?
Tasso: Atlas stands on the back of a turtle.
Dimitri: But what does the turtle stand on?
Tasso: Another turtle.
Dimitri: And what does that turtle stand one?
Tasso: My dear Dimitri, it’s turtles all the way down!

Recursion Theorem

(Kleene – Recursion Theorem) For any computable function
f there exists an e with \phi_e = \phi_{f(e)}.


We define a partial recursive function \theta by \theta(u,x) = \phi_{\phi_u (u)} (x) . By s-m-n theorem or parameter theorem, we can find a recursive function d such that

\forall u: \phi_{d(u)}(x)=\theta(u,x) for \forall x.

Let \phi_v = f \circ d, choose e=d(v) then we have

\phi_e(x) = \phi_{d(v)}(x) = \theta(v,x) = \phi_{\phi_v (v)} (x) = \phi_{f \circ d(v)}(x) = \phi_{f(e)}(x)

Using recursion theorem, we have a beautiful proof for Rice’s Theorem.

Let C be a class of partial recursive functions. Set \left\{e | \phi_e \in C \right\} is recursive, if and only if C = \emptyset or C contains all partial recursive functions.


C = \emptyset or C = \mathbb{N} is trivial. We proof the case C \ne \emptyset and C \ne \mathbb{N}.

Denote  S = \left\{e | \phi_e \in C \right\}.

Exist e_0 \in S and e_1 \in \neg S. If S = \left\{e | \phi_e \in C \right\} is recursive, the following function is also recursive:

f(x) = \left\{ {\begin{array}{*{20}c}  {e_0 : x \in \neg S} \\  {e_1 : x \in S} \\  \end{array}} \right.

By recursion theorem, \exists e': \phi_e' =\phi_{f(e')}. We consider 2 cases:

  1. e' \in S, by index property we have f(e') \in S, so e_1 \in S by the definition of f. We get contradiction.
  2. e' \in \neg S, by index property f(e') \in \neg S, so e_0 \in \neg S by the definition of f. Again we arrive to contradiction.


Why’s recursion theorem interesting? A typical application of recursion theorem is to find a function that can print itself. Let’s say print(*program*) is that function. The output of print(*program*) is not *program* but the function that excuses print(*program*). In other words, we could ask if there is a function which can be self-conscious. I like to call it function-ception, which can be related to inception: does one know that he is dreaming in his dream?

Kleene recursion theorem offers an answer to our question: there is a function-ception, or a program that can print itself. We’ll construct such that function.

Let \phi_e = \pi_1^2, \pi_i^n is the projection function \pi_i^n(x_1,...,x_n) = x_i.

By s-m-n theorem, there is total recursive function s(e,x) such that \phi_{s(e,x)}(y)=\phi_e(x,y).  Let g(x) = s(e,x). Apply Kleene recursion theorem, there is a number n such that \phi_{g(n)} = \phi_n.

For each x: \phi_n(x) = \phi_{g(n)}(x) = \phi_{s(e,n)}(x) = \phi_e(n,x) = \pi_1^2 = n

My work here is done!

How many fixed points does a recursive function f have?

Intuitively, we can see that a (total) recursive function f has infinite fixed points. Recall the proof for Kleene recursion theorem, when we choose v: \phi_v = f \circ d. There is an infinite number of v having that property. Analogically , there is an infinite number of ways to  implement (write code) a function (by adding comments, using different variable names, …)

Now let’s work on some exercises using recursion theorem.

Lemma: There is a number n \in \mathbb{N}, such that W_n = \left\{ n \right\}

We need to find a function \phi_n that is only defined for input n and undefined on the rest of natural numbers \mathbb{N}-{n}

I’m doing this in reversing way (how my thought leads me to the solution). By recursion theorem, \exists n : \phi_n(x) = \phi_{f(n)}(x) = \phi_{s(e,n)}(x) = \phi_e(n,x).

Let g(x,y)  is the function that it is only defined for (x,y) such that x=y. Such an g(x,y) can be constructed as following:

g(x,y) = \left\lfloor {\frac{1}{{\neg sign\left( {\left| {x - y} \right|} \right)}}} \right\rfloor

My work here is done. There is an index e such that \phi_e(x,y) = g(x,y), by s-m-n theorem there is a total recursive function s: \phi_{s(e,x)}(y) = \phi_e(x,y). Let f(x) = s(e,x), and the last step is trivial.

Lemma: There is a number n \in \mathbb{N}, such that \phi_n = \lambda x[n]

With the same line of proof for the previous lemma, we only need to construct a partial recursive function g(x,y) = x \forall y. One can easily recognize g(x,y) is a projection function \pi_1^2

Hello world!

I started Clojure past few days. Thanks to Jo and Milos, my nerdy classmates who are big fans of functional programing. Now I’m getting into it.
I heard of functional programming years ago, I played with Haskell but not much. Probably, the main reason I started liking Clojure because of Computational Complexity course I’ve taken at Charles University.

To be honest, I hated this course at the beginning. Machine Turing is not that bad, NP-complete and reduction techniques are pretty much fun, but recursive function and λ-calculus are so fucked up. I did hate all the lambda notations and hazy proofs with old math style.

I still hate λ-calculus if I don’t have to study for the exam. After several group studies with Jo, and he kept telling me how much he likes Scala and functional programing I thought “Hey, that’s pretty much similar to what we’re studying, you know, recursive functions and other stuff”

Yes, I like Clojure because I like λ-calculus, recursive function, partial recursive function, Kleene theorem and all other stuff. I decided to learn Clojure seriously, so I come up with an idea that I’m gonna blog about it. Of course, not only Clojure, FP but all other stuffs I like such as Computational Complexity, Machine Learning, Computational Linguistics, Lomography and so on.

Why is the blog named MyLomoWalk? I love Lomography, and Lomography is the art of coincidence. I’m a big fan of uncertainty, which often leads to coincidence. MyLomoWalk is my walk in the uncertain universe (or multiverse?)