The biggest challenge of homeschooling is letting go of push and waiting for pull. It is really hard to remain patient when kids are goofing off. The instinct is to push more things at them in the hope that they will pick one of these up and run with them. And it is easy to be afraid that without push they will never discover the thing that unlocks their intrinsic motivation. Yet the reverse may very well be true — anything pushed at them they will wind up not liking even if it would have been their thing had they discovered it on their own. There is little else one can do other to remind oneself to be patient and to create opportunities for moments of wonder and discovery.
Last Tech Tuesday, I introduced the halting problem. As you may recall the upshot was that there is no general algorithm that will determine whether a Turing Machine will stop for a particular input. Now you might at first think that this is not a big deal. After all do we really care if a Turing machine stops or not? As it turns out the implications of this are significant including philosophical limits on what is knowable (to humans) and the practical impossibility of building secure computer systems.
To understand why, let’s recall that when I introduced Turing Machines, I mentioned that “to date we have not found a model of computation that is more powerful than a Turing Machine.” Now let’s turn this on its head and ask whether or not most existing programming languages and computer designs are as powerful as a Turing Machine. The requirements turn out to be super simple: all you really need is conditional branching, i.e. testing a condition and doing one thing if it is met and another if it is not (see my post on control structures) and variables (technically infinitely many variables but we will see more about that in the future). Most languages have that and so most languages are what is called Turing complete.
That it turn implies that our halting problem applies to most programming languages and thus there is no general algorithm to determine whether a program will stop on a particular input or not. But the problem is way worse than that. Seemingly trivial questions such as “will this program output the number 42?” or “will this program ever execute line 42 of its code?” can be reduced to the halting problem. Put differently, if there was a general algorithm to determine the results for these questions then it could be used to solve the halting problem. Since we know that the halting problem cannot be solved the reduction shows that these problem also cannot be decided with a general algorithm.
Putting Turing completeness together with the ability to reduce other problems to the halting problem we are faced with a very unsatisfying situation: there really isn’t much we can say about what programs do! One of the dramatic practical implications of this is that computer security is kind of an impossible task. As long as we allow general programs (meaning programs in a Turing complete language, i.e. pretty much any general purpose language) we can’t make sure that they won’t do something nasty once they execute.
Now let’s briefly consider a possible philosophical implication of the halting problem. The universe itself (and even smaller physical processes inside of it) can be interpreted as carrying out computations. The halting problem’s undecidability then suggests that many questions cannot be decided by a general algorithm either. That in turn puts a question mark behind the believe in the singularity to the extent that a self learning machine is still applying a general algorithm.
A couple of years ago I wrote about our need for an “opposing view reader" that would intentionally show us commentary from people with opinions different from our own. As far as I can tell relatively little progress has been made on this front. Twitter, for instance, will generally recommend to me that I follow people who are like the people I am already following. So I was happy to see that there is at least some academic research on this topic. The Technology Review mentions a paper titled “Data Portraits: Connecting People of Opposing Views” that is available on arxiv. Unfortunately when I actually read the paper I found that n for their study was tiny (37!) and I don’t think supports the conclusions with any significance (their stats notwithstanding).
In my original post I failed to explain fully why this problem has been growing in importance. One of the fundamental forces of the Internet has been the unbundling of content. If you are reading this right now you are getting my opinion from my blog or in your Tumblr dashboard (or via a feed reader). The post stands by itself. Whatever I link to was chosen by me. Put differently, there is no context that could provide for an opposing view, no additional editorial or purposeful pairing by an editor.
When you combine unbundling with a huge increase in available content, you wind up with a situation where someone could spend all their available time just reading content that will confirm their existing views. Existing recommendation and search algorithms are all built to re-enforce this by trying to present you with content (or people) that match your interests. That leads to what Eli Pariser has called the “filter bubble” — his TED talk on the subject is worth watching (or you can read his book).
I also should have given credit to my then fellow PhD student and now BU Professor Marshall van Alstyne who wrote an excellent paper on the subject as far back as 1996, titled “Global Village or Cyber Balkans?” (co-authored with Erik Brynjolffson). Here is a great quote from the introduction:
Information technology can link geographically separated people and help them locate interesting or compatible resources. Although these attributes have the potential to bridge gaps and unite communities, they also have the potential to fragment interaction and divide groups by leading people to spend more time on special interests and by screening out less preferred contact.
The paper itself is quite theoretical but I am pretty sure that today we could easily use Twitter data to examine the hypothesis.
If you know of a recommendation service that does in fact surface opposite views please let me know. I am also interested in additional research on the topic. In the meantime I am thankful for folks like David Pinsen whom I follow on Twitter and who routinely helps challenge my thinking.
Thanksgiving is my favorite holiday. Not only is there no gift giving madness but it is great to be reminded that I have much to thankful for. Last year I wrote a post thanking my parents. This year I want to give a big shoutout to Susan. We met completely randomly in a cafe in Paris in 1991 and if she hadn’t been the one to suggest that we meet again the next day our lives would likely be very different!
There are so many things that I am thankful to Susan for but two in particular stand out. The first is that she was at all times a steadfast supporter of my entrepreneurial endeavors, even when those did not pan out (which was more than once early on!). Given how crazy working on and with startups can be it is impossible to overstate how important this has been. I am certain I wouldn’t be a partner at USV today if it weren’t for Susan’s support (I am now trying to return some of that as Susan is on her second startup with Ziggeo).
The second is that Susan is always up for trying out something relatively crazy. The latest example of this is our experiment with homeschooling our children. And Susan does so providing the perfect emotional balance to my somewhat manic drive to just get things done.
So on this Thanksgiving: thank you Susan.
PS I love you!
Two previous Homeschool Wednesdays covered the relationship between math and beauty as a different way of motivating the study of math. My first presentation was on spirals and the second one on waves. In each case the main point I am trying to make for our kids is how relatively simple mathematical formulas can generate magnificent patterns found in nature. Another area where this is true are fractals. These self similar patterns often have surprisingly simple underlying algorithms:
http://www.eddaardvark.co.uk/python_patterns/images/mbex4_anim.gifUnfortunately the great animated GIFs that I found for the second half don’t render in Slideshare (they work beautifully in Keynote). But you can find them via the links on the last two slides. Here I am embedding the awesome last one which shows 63 levels of zooming into the Mandelbrot set and was created by John Whitehouse (who has many amazing math patterns on his website):
Seeing this has me excited about the deep mystery of how all of this complexity emerges from such simplicity (see Slide 13 above for the equation that drives this). I hope it will have the same effect for our children.
The current sequence of Tech Tuesday posts is about the theory of computation. We have already seen that a simple of model of computation such as the Finite State Machine is very useful but has severe limitations in that it cannot even decide a language as simple as all palindromes. We then learned about the Turing Machine as the most powerful known model of computation and saw how a Universal Turing Machine establishes the separation of software from hardware. This leads to a natural question: what are the limitations to what a Turing machine can compute?
Let’s start with a seemingly simple question. Does a particular Turing machine stop for a given input, i.e. initial state of the tape? This seems initially trivial. After all a Turing Machine only has a finite set of states and we saw that this made it possible to answer this very question for any Finite State Machine. But a Turing Machine also has an infinite tape and that’s where the problem lies. Remember that the transition function for a Turing Machine depends on its state and the symbol in the current square of the tape.
Even with a relatively trivial machine of half a dozen states or though the patterns that can develop on the tape as the machine operates can be incredibly complex (and chaotic). It may take years of investigation to come up with a proof as to whether or not a particular machine stops (see for instance the investigation into so called Busy Beaver machines). So that leads to the obvious question: is there a general way of determining for any Turing Machine whether it will stop? This is known as the “halting problem" and turns out to have far reaching implications for the boundaries of human knowledge.
The answer turns out to be no and Turing proved this in his 1936 paper. I am not going to attempt to reproduce the proof here but will suggest the basic idea. The extreme simplicity of Turing Machines lets us enumerate all programs, which means we can assign a number (i) to each program. Similarly every input to a program can be represented by just a number (x). That let’s us reduce the halting problem to hypothetical halting function h(i, x) which is 1 if the program i halts on input x and 0 if it doesn’t. So now we need to show that such a function cannot in fact be computed.
Let’s consider an arbitrary computable function f(a, b) — meaning a function that takes two inputs and returns an output. From this we can construct a new function g(i) as follows. g(i) is 1 if f(i,i) = 0 and undefined otherwise. Since f(a, b) is computable (by assumption), so is g(i) (this is a bit of hand waiving that we will come back to). Computable means that there is a Turing Machine program that computes g. Given enumerability of programs the program that computes g has a number which we will call e.
Now let’s throw the value e into f and compare that to our posited halting function h. It must be the case that either f(e,e) is 0 or it is not. If f(e, e) is 0 then g(e) is 1 by construction. But since g halts, it would have to be that h(e, e) is 1 (which is different from f). Now conversely if f(e, e) is not 0, then g(e) is undefined, again by construction. Undefined here is implemented by an indefinitely looping program which means that h(e, e) = 0 (again different from f). Recall that f was an arbitrary computable function and yet h (evaluated at e) is different from every f. That shows that h cannot be computable.
This is reminiscent of Cantor’s diagonalization proof for why there are more real numbers than integers. The diagonalization here becomes possible because we have a model of computation that lets us assign a number to each program. And because we can feed that number back to a program (including to itself) we have a way of formalizing what it means for one program to operate on another. This is the true power of Turing’s formulation — it connects programming deeply and elegantly to mathematics. We can now use one to analyze the other and in the process see the limitations of both. Next Tuesday we will investigate some of the philosophical and practical implications of the non-computability of the halting problem.
In my personal public markets portfolio I am long a number of robotics companies because I see robotics as one of the big secular trends that’s investible. As we are getting more and more robots in different form factors (including drones and even 3D printers), I am curious whether there is a need for a realtime OS. I would love to hear from folks active in these communities to learn what they are using and what they see as promising. For instance, is anything on this Wikipedia list exciting? Anything else to look at? Also, is this even a separate opportunity or will some version of Linux do just fine?
I am a bit of a grinch around the holidays as I really don’t like getting more stuff. As a result I am also not all that excited about buying stuff for other people. Thankfully this year there is a terrific solution — gift cards from Skillshare and from Shapeways. With these you can give the gift of learning and discovery! What could be better? The recipients can of course take any class or buy any item but when you give both, they can first take the Introduction to 3D Printing on Skillshare and then design and print their own item on Shapeways.
Facebook goes public and its stock declines. Commentators write that investors should have known it was overpriced. Twitter goes public and its stock pops. Commentators write that the company left money on the table. Not nearly enough people though remark on how crazy it is that companies still go public the way they do. Three years ago I wrote a post saying that I was hoping we would see IPO 2.0 and unfortunately I am still waiting.
What do I mean? Building a complete order book upfront and allowing retail investors to participate in that process directly. This is entirely possible with today’s technology. People place limit orders to buy through their brokerage account all day long — but we use this only for companies that are already public. The same mechanism could be used to build a book before a company is public.
This would be desirable for two reasons. First, a complete book would make pricing the IPO way easier because it would reveal much more information about the shape of the demand curve. Second, this would give retail investors direct access without the allocation game being played by the intermediary banks and brokers which still (again) direct on the basis of the relative importance of customers to them.
Now is a good time to remind everyone that this isn’t hypothetical but that in fact Google did go public this way. My previous hope was for another company to have the same courage that Google did. But maybe it is time for regulators to wake up and make the direct IPO mandatory. The current gatekeepers for the process unfortunately have no interest in real change and this is an oligopolistic market where we cannot sit around and wait for competition to solve the problem.
Today I will be participating in a discussion at NYU on the future of higher education. The panel that I will be on has been given the following questions: “Do universities provide good value for money today? What are the gaps in the higher ed ecosystem, and who will fill them?” As it turns out these are the wrong questions to ask and I am planning to explain that in my introductory remarks.
Universities got going almost a thousand years ago with the founding of the University of Bologna in 1088 and Oxford got started not quite a hundred years later. The European system was well established by the end of the 18th century with over one hundred active universities. Not much has changed in the fundamental model of a university since then: it combines teaching and research and is organized by along faculty lines.
Back then in order to hear someone speak you had to be in the same room at the same time (and preferably close to the speaker). When you wanted to read a book you had to be in the library with the one copy that was kept there. In addition, travel was quite arduous and slow. With that kind of “production technology” it made sense to bundle research with instruction, bundle lots of disciplines and bundle a whole education in time (meaning a four year degree).
So what you were getting as a student was a package price. Nobody was offering anything a la carte as it couldn’t be delivered that way. We are now just at the beginning of the great unbundling of higher education. It will be unbundled into much smaller units — with a “course” being just one of the possible unbundled units. Other units that come to mind are intensive seminars, research facilities (cf. Science Exchange), published results down to data sets, and so on.
Newspapers similarly were a bundle of different types of information that existed largely because it was expensive to print and distribute. We have seen the effects of unbundling there and they are still ongoing. I similarly expect the unbundling of the university to take a long time but I am convinced that over time it will be dramatic reaching all the way to the existing definitions of faculties as the existing grouping such as biology, chemistry, physics, etc are no longer meaningful.
These unbundled units will increasingly compete in a global marketplace. That will expose many of them as unnecessarily duplicative and often of inferior quality both on the teaching and research side. The consequences will be an implosion in the size of the “university sector” on par with that in newspaper publishing. So instead the questions that we should be asking are the following: “who will be providing value tomorrow?”, “how will that value be financed / paid for?” and finally “what opportunities exist for re-aggregating the unbundled pieces?”
I am looking forward to the discussion. If you are interested and want to follow along, there will be a livestream.