Jeffrey Kegler

I'm a computer programmer who lives in Northern California.  I've been using UNIX and C since 1977, before UNIX's first commercial release, and Perl since it's first release in 1987.  I'm a published mathematician, if just barely, and I've written a novel based on some of Kurt Gödel's work.  I have a BA and an MSCS from Yale and was a Lecturer at the Yale Medical School.

For the past few years, I've been writing an open-source Perl module that does general BNF parsing.  For many years, I had an independent practice as Algorists, Inc.  More recently I've worked at Applied Materials and Sun.  For more, see my CV.

Marpa, a Context-free Parser

My major interest at the moment is Marpa, a parsing algorithm I have developed based on the work of Jay Earley and others.  I point to much more about Marpa on its own page.

Perl Parsing is Undecidable

I am credited with the proof that Perl parsing is undecidable in, among other places, the Wikipedia article on programming languages.  While not completely unexpected, but this discovery did surprise a lot of people initially.

For most computer languages, although the run-phase behavior might be undecidable, it is always possible to determine if the source code is well-formed.  If so, it is always possible to produce a unique parse from that source code.  Perl is unusual in that not only is its run phase behavior undecidable, so is its compile phase behavior.

But if you're not used to the Larry Wall language design philosophy, you may be wondering.  Why create a language that is not, in general, parseable?  The answer is that Perl in the compile phase allows the programmer its full range of programming capabilities.  These allow Perl a lot of flexibility in setting itself up.  But whenever you have all the capabilities of a Turing-complete language, you have undecidability.

I lay out the details of the proof in three articles in The Perl Review.  The articles assume no math background.

My Novel, The God Proof

I've written a novel about Kurt Gödel.  Those of you into software probably know Gödel for his mathematical work.  Gödel also discovered a new proof of God's existence.  A sketch of Gödel's "Ontological Proof", as it is usually called, is in his Collected Works (Vol. III, p. 403-404), but two of Gödel's notebooks have disappeared.  Based on their dates and titles, they likely contained more about the God Proof than we now have.  The God Proof begins with the reappearance of the Lost Gödel Notebooks in Pacific Grove, California.  You can download the novel for free from this site or from my Lulu storefront.  You can also buy it at Lulu or from Amazon.com.  There's more about The God Proof here.

I've never heard of anyone being persuaded by a proof of God's existence, whether by Kurt Gödel or anyone else.  A proof that can change someone's mind is called "coercive".  There are lots of coercive proofs out there.  For example, if you doubt the facts of arithmetic, there are convincing arguments, backed up by the fact that you'd be wise to accept their force if you want correct change.  Similarly for a lot of the basic facts of geometry.

Could a coercive proof be made for God's existence?  A reasonable person can certainly have her doubts.  But you'd also be forced to admit that if any mathematician could come up with an unexpected results, it would be Gödel, who made a career out of them.

Kurt Gödel's Citizenship Hearing

The most famous incident in Kurt Gödel's life is his citizenship hearing.  There are many versions of this story.  Most agreed on the following:  Studying for the hearing, Kurt Gödel became obsessive.  He looked very closely at the U.S. Constitution.  He decided it contained a contradiction, one which would allow the United States to be turned, quite legally, into a dictatorship.  Gödel decided that his discovery needed to be shared. Albert Einstein and Oskar Morgenstern, Gödel's two best friends and his witnesses at the hearing, teamed up to distract Gödel.  But the hearing was barely underway when the judge observed that Gödel's native Austria had become a dictatorship, and that we should be grateful this cannot happen in the U.S.  To his friends’ horror, Gödel quickly started to correct the judge.

There was a problem with this story as history -- every version of it was hearsay.  And they all had the sound of tales "improved" in the telling.  Of the four people at the hearing, only one, Oskar Morgenstern, was thought to have left a first-hand account.  He was said to have written the story up for publication. But if the Lost Morgenstern Document had ever existed, three decades ago it went missing.  And it stayed missing until I found it in November 2008.

I admit it.  I'm a sucker for the "lost document" trope.  That's why I plotted a whole novel around two lost Gödel documents.  So for me to find an important lost Gödel document sounds a lot like the premise of "Murder She Wrote" -- a TV series where every week a mystery writer supposedly solves a real life murder.  It's an amusing idea, but it doesn't seem very probable.

But strange or not, it happened.  I've put the Lost Morgenstern Document on the web, and I'm blogging the story of how I found it.

Publications

  • "Perl and Undecidability", 2008, a three part series in The Perl Review.  See above.  Also, look here for more, including downloadable versions.
  • The God Proof, 2007.  My novel based on Kurt Gödel's Ontological Proof.  See above.
  • ”A Polynomial Time Generator for Minimal Perfect Hash Functions,” Communications of the ACM, vol. 29, no. 6, pp. 556-557, 1986.  My lone refereed mathematical publication.  At the time CD's were new and there was a lot of interest in pre-processing fast, "perfect" hashes ahead of time.  CD's weren't writable in those days.  So folks said to themselves and each other, "Why not take advantage of the fact that the database can't be dynamic, and pre-process the keys to produce a really fast, custom search algorithm?"  This short paper proved that there's nothing to be gained by pre-processing the hash algorithm for a static database.  It was a bit of a surprise.
  • As co-author, thirty books in Urban Land Institute’s Dollars and Cents of Shopping Centers series for 1990, 1993, 1995, 1997 and 1998.  I'm listed as an "institutional author", under the name of the company I owned (Algorists, Inc.), but Amazon figured out who I was.  For decade-old shopping center statistics, these books are the last word, probably literally.

The Ocean of Awareness Blog

I write a well-received blog, Ocean of Awareness, which focuses on Marpa, parsing, Perl and things of interest to techies.  Its name is taken from a Tibetan saint.  Ocean thrived in the 11th century and is one of the characters in the God Proof.

I also have a non-technical blog, called the Ontological Blog.  Well, I call it mine.  Actually, it came into existence because its nature requires it.  Marpa has been my main focus in the recent past, and I have not posted to this blog in a while.

Links

My pages: Ocean of Awareness (my technical blog) | CPAN | Perlmonks | LinkedIn | Ontological blog

God Proof pages: Lulu Storefront | Createspace Storefront | Amazon Storefront



Comments