Sunday, April 2, 2017

Problems with self-reference and recursion (Aronson's sequence)

The most delicious, frolicksomely frustrating things to think about are the problems which reference themselves. Recursion is such a twisted mind-trap. Having just exposed my class to the joys of the halting problem (animated video explanation), and using it to show that all sorts of other problems cannot be solved --- one of the duties of professorhood is teaching students how to solve problems, but the peculiarities of my work are that I teach students which problems they can't solve --- I was delighted to read a snippet about Aronson's sequence:
‘T’ is the first, fourth, eleventh, sixteenth, twenty-fourth, twenty-ninth, thirty-third …
Here's the introduction on Futility Closet.

Here is Aronson's sequence on the Online Encyclopedia of Integer Sequences (one of my favorite sites!).

I want to know how the sentence ends, but of course the sentence can't end as long as I'm stuck thinking about the way I expect it to end. I'm sure that some sufficiently proficient linguist-mathematician team could come up with a satisfactory, and finite, end to the sentence. I'd buy that book!


This post's theme word is pabulum (noun), "bland intellectual fare: insipid or simplistic ideas, entertainment, writing, etc." Using the word "fare" makes me think of other food analogies. The collection of results stemming from Gödel's (In)Completeness Theorems are savory intellectual nuggets, with not a morsel of pabulum.