Archive for August, 2009

Goldbach’s Conjecture, Turing Machines, and Artificial Intelligence

Thursday, August 20th, 2009
When I was a graduate student I’d work on proving Goldbach’s Conjecture when I needed a break from my real research. I’d focus on what this Wikipedia article (http://en.wikipedia.org/wiki/Goldbach’s_conjecture) calls the strong form : every even natural number (aka even positive integer) greater than 5 can be expressed as the sum of two prime numbers. So, for example, 6 = 3 + 3, 8 = 5 + 3, 10 = 5 + 5 (and 7 + 3), 12 = 7 + 5, …. Again, this is a conjecture that is believed to be true by virtually everone and its truth has been demonstrated with computers up to huge even numbers, but no one has proved its truth for all even numbers, and there are an infinity of them.   

The really attractive thing about number theory is that so many of the problems are so easy to understand by so many — you may not be able to solve the problem, but you sure understand what’s being asked! An approach I hit upon to prove Goldbach’s conjecture (or I suppose disprove it, or perhaps that you could’nt prove it one way or the other!) was essentially this, write a computer program that ran forever (if you were to run it), generating the even natural numbers one after the other, and write another computer program that ran forever (again, only if you were to actually run it), that generated all the sums of two primes “in sequence”, and then show that the two programs were equivalent. Unfortunately, that last step is REALLY, REALLY hard, if doable at all, but fortunately my PhD research took off about this time and I did that instead, much to the relief of my wife, parents, and in-laws!

But now, just as I want my artificial intelligence students to find projects of interest, this is the project that I want to return to. Its been about 3 years since I’ve done my own substantive computer programming, and its probably been 15 years since I’ve done substantive programming in the LISP language. So this will be fun! I can trivially write a program that generates all even natural numbers greater than 5: (defun GenEven () (do ((i 3 (+ 1 i))) (t (princ (* 2 i))))). A program that generates the sum of all pairs of primes is a good deal more complicated, because in general each addend needs to be verified as prime (http://en.wikipedia.org/wiki/Prime_number). In fact, one way to write this second program is simply to write a program that generates all prime numbers, and then “append” it to a copy of itself, and as each copy produces a prime the sum is output. However we write the second, what we imagine is something remarkable — that the latter very complicated program is equivalent to the former very simple program. And if you’ve taken formal languages and automata theory, you probably know that this is an example of the concatenation of an unrestricted (and non-context free) language with itself being equivalent to a regular language!

It would be tempting to spend a good deal of time making each of these programs as concise or as efficient as possible, but you see, I am never going to run either program. If I am biased in any direction it is that each program be as “unstructured” and as “primitive” as possible, because once these programs are defined, a third program, an AI program, is going to search for a sequence of rewrites that will transform one program into the other, while provably maintaining the original functionality of each. The third (AI) program is the one that will actually be run, and I’ll be writing this program in Lisp. But the two programs, one for generating the even numbers and one for generating the sums of prime pairs, I’m imagining will be written in the most primitive of languages — the language for programming (or defining) a Turing Machine — a simple form of computer, but not a computer that you would ever power up — a Turing Machine is strictly a theoretical device (http://en.wikipedia.org/wiki/Turing_machine).
The reason for the bias of starting with as unstructured and primitive as programs as possible is that though there are optimizations in the test for primality, for example, which I could reflect in my initial programs, these optimizations reflect patterns that almost certainly have been exploited in explorations of Goldbach’s conjecture by better minds than mine. It may be that any proof, if one is possible, has to rely on reasoning that is just off (human-conceived) map.
I’d actually started this process as a grad, exploring the ways to bridge these two programs, via an AI program that searched through billions of possible rewrites. I’m essentially an experimentalist and I start with code and looking for data — that’s my bread and butter. I think that what I am really doing is shaping my retirement 20 years from now (or less, for Pete’s sake). When friends visit and ask Pat where I am, she’ll point to the shed and tell them that I’m working on “that proof”.  More likely, I’ll be tinkering with the AI program, making sure that there are no bugs in it — can you imagine my despair, if near the end of my life and after searching billions of rewrites, my program comes back with “Proof Found!”, and I didn’t correctly save the path my AI program took to get there!?
The older I get, the more I remind myself of my father. 

 

Artificial intelligence, critical thinking, and Facebook friend suggestions

Sunday, August 16th, 2009
This fall I’ll be “teaching” Vanderbilt’s undergraduate course in artificial intelligence (AI) at a physical distance — from Arlington, VA. It’s an opportunity to shatter the way I’ve taught AI in the past. As uncomfortable as giving up the ol’ PowerPoint presentations are, and as creative an outlet as it was to prepare and still is to refine/adapt those slides (I’m absolutely serious — those slides are sometimes art — I’m seriouuuuuuus!), I’ve fallen back on them too much — they’ve encouraged an automaticity of teaching and a psychological distance from students that is not healthy. Gutsy was/is the professor that attempts a proof or writes a program for the first time (perhaps, in a long time) on a board in front of a class. And so long as the class recognizes that they are witnessing a search for an answer rather than an answer, its a-OK: “I’m about to demonstrate what it is to search for a proof, with some commentary, I hope, about how this search is systematic in advancing towards an answer, and if I/we don’t find the proof today, you and I can race to see who can post a valid proof by next week.” It’s scary, quite frankly. I think its possible that a fair number of professors got into academia, in part, because they saw a safe psychological distance modeled in the classrooms in which they were students.

Prefabricated slides also add friction that opposes mobility — if my slides are synced to a textbook, for example, it’s harder to switch textbooks if I feel obligated to prepare yet another set of slides, or even to adapt my current slides to the new text.

When I started this post, I really wasn’t intending to get into the above, but rather launch directly into some ideas that are arising as I think about the AI course as critical thinking “lab” — as we study ways of designing ‘intelligent’ computers, we reflect on our own thinking — for inspiration, comparison, and validation. My study of AI, and in fact computer science generally, has certainly shaped the way I think about my thinking and the thinking of others, but frankly its shaped my thinking itself — I’m quite certain that I think differently than I would have if I had gone to Humboldt State to study forestry, though probably not radically different.

As critical thinking lab I want to reflect on everyday scenarios (and not so everyday scenarios too). Not long ago my sister posted a status report on Facebook on how eerie it was that Facebook was making friend suggestions that were spot on — that is, she knew them, but she had no idea how Facebook would know that! This is certainly the case with me. There are, of course, friend suggestions that seem no brainers — e.g., I and suggested person X have 2 friends in common. Sometimes these no brainer suggestions have a plausibility, but in other cases they are not terribly suggestions, and Facebook has enough information to infer this — if the two common friends are married and there is no other substantive link between me and the suggested person that I can see, this suggestion loses credibility as someone I might reflect on, and if Facebook knows of the marriage link between the two common friends, you would think that their algorithms could be written to take this into account (and perhaps the algorithms do!?).

The mystery of course is in the suggestions on which I am clueless on how Facebook made a connection — do they have some kind of crystal ball? :-) Two clues as to what Facebook could do if they chose to do so appear in the Facebook margins itself. One is this app that keeps popping up — “Find out who is searching for you!”, with a very good-looking young woman smiling out at me :-) ). Who knows, maybe the app is a scam, but is does suggest that who I search for and who’s profile I am clicking on (including perhaps through a Google search result) is recorded, and why wouldn’t it be!? It also seems clear that the ads that pop up in the margins are customized to me in some fashion (e.g., “Eating out in DC?” “Class of 1975 memories”). So, why couldn’t friend suggestions take into account who/what I’ve searched for and who’s (partal) profile I’ve gone too? — I just went to the “Glendora High School Class of 1975″ site and clicked on a couple of non-friend people (”Is this Betty Friedland the Betty Moorehead that I had a crush on in first grade??!!”) Now, it seems unlikely that having looked at Betty’s partial profile and having not friended her that she would be suggested as a friend for me (but I’ll let you know). But is Betty Friedland going to see my name as a suggested friend? Or more generally will that I looked at Betty Friedland be a factor that’s taken into account in friend suggestions to Betty? I don’t know, but I’d like my students to be asking themselves these kinds of questions on everyday kinds of scenarios like this. Exercises like this (a) cast a light on my own thinking, (b) suggest what others can infer and what can be automated (because whatever I can infer from Facebook data can be inferred by others and by properly designed automated methods), and (c) beg some interesting ethical discussions concerning AI (and in this case, online social networks). In the context of AI there are a lot of mundane things that one can infer about me — e.g., I’m not part of the Washington DC network, but given my photo gallery and many of my friends, it’s not hard (for a human) to realize where I am living right now, though to program a computer to take these modest inferential steps would be quite interesting. And there are even more ambitious inferential leaps that can be made, by human and (thus) ultimately by computer — there are all kinds of research going on into what can be inferred from social networks, and exploring designs that guard against those inferences.

At age 52, I am a lot less concerned with my own privacy than (I think) I used to be — life is short as I’ve been aware of lately, and while I am much more self-revealing than I once was, I keep a low profile on politics and religion, at least so long as I’m in this government gig, though you could dig, but I don’t think a simple story would be revealed (though the simplicity of the story often has more to do with the “reader” than the “author”). I think that I might prefer automated inference methods that include explicit representation of uncertainty to human inference methods that sometimes (incorrectly) dismiss the uncertainty — of late uncertainty has been much more a friend than an enemy. To return to my original thread, however, I see online social networks as a treasure trove for AI class discussions. Music and environment are others. More to come, I expect.