Corn Maze 2

It is now officially a tradition.  Our bible study group went to a corn maze for the second year in a row. Last year was my first corn maze ever.

Once again, someone recorded our progress via GPS.

This year, we went to the corn maze at Schuster's Farm.  The maze comes in two phases.  The first phase begins and ends in the bottom right corner.  The second phase begins and ends right above the "Ronald McDonald House" logo.

They give you a full map and 10 quiz questions.  There are 10 posts at forks in the path within the maze.  Answering the quiz question correct tells you which way to go.  I was also guiding us by looking at the full map during all of phase one and the beginning of phase two.  Then someone suggested that we try it without looking at the full map.  We soon got lost in the middle of the maze by going in a circle.

We continued to not use the full map until we were in the bottom-left corner.  At this point, I was completely confused about where we were supposed to go next.  I feel like the single blue circle in that area does not correctly reflect how lost I thought we were.  Since the group wanted to be done soon, we decided to look at the full map again.  I could not figure out where we were, but someone did and they quickly got us back on track.  From here, we continued using the full map and headed straight for the exit.

I liked last year's maze better.  Recall that last year, the game was that they give you (part of) the map and you need to get to certain checkpoints (where you get more of the map).  Even with the map, it was very difficult to know where you were.

Once again, I am excited to go to a corn maze next year.

Can humans solve the halting problem?

In Wikipedia's article on the halting problem, there used to be a section called "Can humans solve the halting problem?" but I just noticed that it was deleted in 2008. There was minimal discussion about this deletion after it happened, and I would have voiced my opinion to keep the section had I noticed. However, instead of going through the necessary steps to reintroduce the content, I will just paste (most) of the section here.


Can humans solve the halting problem?
It might seem like humans could solve the halting problem. After all, a programmer can often look at a program and tell whether it will halt. It is useful to understand why this cannot be true. For simplicity, we will consider the halting problem for programs with no input, which is also undecidable.

To "solve" the halting problem means to be able to look at ''any'' program and tell whether it halts. It is not enough to be able to look at ''some'' programs and decide. Even for simple programs, it isn't clear that humans can always tell whether they halt. For example, we might ask if this pseudocode function, which corresponds to a particular Turing machine, ever halts:

function searchForOddPerfectNumber()
  var int n = 1    // arbitrary-precision integer
  loop {
    var int sumOfFactors = 0
    for factor from 1 to n - 1 {
      if factor is a factor of n then
        sumOfFactors = sumOfFactors + factor
    }
    if sumOfFactors = n then
      exit loop
    n = n + 2
  }
  return

This program searches until it finds an odd perfect number, then halts. It halts if and only if such a number exists, which is a major open question in mathematics. So, after centuries of work, mathematicians have yet to discover whether a simple, ten-line program halts. This makes it difficult to see how humans could solve the halting problem.

More generally, it's usually easy to see how to write a simple brute-force search program that looks for counterexamples to any particular conjecture in number theory; if the program finds a counterexample, it stops and prints out the counterexample, and otherwise it keeps searching forever.  For example, consider the famous (and still unsolved) twin prime conjecture. This asks whether there are arbitrarily large prime numbers p and q with p+2 = q.  Now consider the following program, which accepts an input N:

function findTwinPrimeAbove(int N)
  int p = N
  loop
    if p is prime and p + 2 is prime then
      return
    else
      p = p + 1

This program searches for twin primes p and p+2 both at least as large as N.  If there are arbitrarily large twin primes, it will halt for all possible inputs.  But if there is a largest pair of twin primes P and P+2, then the program will never halt if it is given an input N larger than P.  Thus if we could answer the question of whether this program halts on all inputs, we would have the long-sought answer to the twin prime conjecture.   It's similarly straightforward to write programs which halt depending on the truth or falsehood for many other conjectures of number theory.

The UNO T-Shirt Offer

Back in November 2011, my wife and I spent Thanksgiving at her parent's house. While there, we played an old fashion game of UNO. I don't think I won the whole time.

Although the cards appeared to be in mint condition, I couldn't help but notice that they were older than me!

Check out that expiration date: 2/28/82!

Ah, the good-old days...when you could buy a t-shirt for $4.95 and that INCLUDED "postage and handling".

Compliance Suggestion for Google

A court in Paris, France has fined Google $65,000 because its search engine's autocomplete feature brings up the French word for "crook" when users type the name of insurance company Lyonnaise de Garantie, which brought a suit against Google.

(Source: Ars Technica - French court frowns on Google autocomplete, issues $65,000 fine)

First of all, that is not Google's choice. The autocomplete suggestions are based on what other people are searching. Thus, loads of French people already associate Lyonnaise de Garantie with "stealing their money".

Ok, so the French court is foolish, but Google still needs to comply with the ruling. It appears they did the obvious and now prevent their autocomplete from displaying any query containing both "Lyonnaise de Garantie" and "escroc" (the French word for crook). I have a better idea.

Google should

• prevent their autocomplete from displaying any query containing "Lyonnaise de Garantie",
• prevent their search engine from accepting any query containing "Lyonnaise de Garantie", and
• remove search results (from allowed queries) that contain any reference to "Lyonnaise de Garantie".

That way, Lyonnaise de Garantie can't be offended and sue Google for connecting their name with any negative connotation this world has to offer.

Sounds like a good idea to me.

Closing Time?

Over the previous year, I went to two restaurants with the following posted hours, respectively:

Of course the object of interest is their closing time, or lack thereof.

I can just picture an Abbott and Costello bit going something like this:

Me: What time do you close.

Waitress: When we close.

Me: Yes, when do you close.

Waitress: When we close.

Me: Yes, yes. That is my question. When does this restaurant close?

Waitress: Our restaurant closes when it closes.

Me: Of course it closes when it closes. I am asking you at what time it closes.

Waitress: The closing time is when it closes.

Me: *sigh*

Above the Law

Some people must think that they are above the law.


Here is the closeup:



(In reality, this is at the beginning of a walking bridge over a busy street and the city probably does not want signs to distract drivers. However, the plan reading is so much funnier.)

The Trinity is Antitransitive

I grew up going to St. James United Methodist Church in Sioux City, Iowa. Every time I return home and attend church there, I rethink many of the thoughts that I have had in that building over the years.

One of those thoughts is that I have always liked one of the stained glass windows next to the pew in which my family regularly sits.

In particular, I have always liked the visual representation of the relationships in the trinity.

However, I have never known why I liked it...until now!

The Trinity is an antitransitive relation.

Now, to explain what that means.

A relation is the formal mathematical notion most closely related to the word I used before, "relationship". In the case of the Trinity relation, each pair of (distinct) words (i.e. God, Father, Jesus, Holy Spirit) is ascribed either "is" or "is not" (so the Trinity relation is a binary relation). (For each pair of identical words, the window does not state the relationship but it is implied that each word is related to itself, thus ascribed an "is" and making it a symmetric relation.)

To understand an antitransitive relation, it helps to know what a transitive relation is. A (binary) relation is transitive if

for all words x, y, and z, if x is related to y and y is related to z, then x is related to z.

The most commonly known transitive relation is the equivalence relation. As everyone knows, if x is equal to y and y is equal to z, then x is equal to z.

An antitransitive relation has the exact opposite conclusion about every triple of words. A (binary) relation is antitransitive if

for all words x, y, and z, if x is related to y and y is related to z, then x is NOT related to z.

Although somewhat counterintuitive, I believe it is the mathematical beauty of the Trinity that drew me to this window all those years ago.

(Or maybe it is because it also looks like a planar embedding of K₄...nah.)