Joel David Hamkins: observation

Transcript context

…Yeah …given a configuration, and you ask, “Will this particular cell ever, you know, be alive—” …in the evolution?” And you can prove that that question is equivalent to the halting problem. It’s computably undecidable. It’s semi-decidable in the sense that if it will become alive, then you will know it at a finite stage because you could just run the Game of Life algorithm and let it run. And if it ever did come alive, you could say, “Yeah, it was alive.” But if you’ve run it for a thousand years and it hasn’t come alive yet, then you don’t necessarily seem to have any basis for saying, “No, it won’t ever come alive,” if the behavior was very complicated. Maybe if you have a complete understanding of the evolution of the behavior, then you can say no, but you can prove you won’t always have that understanding— …precisely because the problem is equivalent to the halting problem. And nevertheless, when you sit back and look and visualize the thing, some little mini cellular automata civilizations are born and die quickly, and some are very predictable and boring, but some have this rich, incredible complexity. And maybe that speaks to a thing I wanted to ask on the halting problem and decidability. You’ve mentioned this thing where if you understand the program deeply, you might be able to say something. So can we say something interesting about, maybe, how many programs, statistically, we know something about in terms of whether they halt or not? Or what does it mean to understand a program deeply enough—…

Stored transcript either side of the excerpt. The highlighted words are the published quote; the surrounding text is unedited source, never generated.