I was reading this article by Scott Aaronson: https://www.scottaaronson.com/blog/?p=2725
I am trying to parse what exactly this means. So you take the Turing machines with at most 8000 inputs (a finite set), then you take the ones that halt (again, now everything is entirely finite). Now you take the maximum over a completely finite set. Everything here is finite. But then somehow you can't take this maximum? Without even going into details of how the object is constructed, why is this not obviously nonsense?
Is the reason that the set of Turing machines that halt is independent of ZFC? I.e. if we had any given set of Turing machines and knew what was in there, we could compute the run time of the longest one.
If the set itself is independent of ZFC, does that mean that ZFC doesn't fully capture all possible sets?
How should I understand this?
Yes, what Aaronson’s student constructed was a Turing machine that halts if and only if ZFC is inconsistent. So if ZFC is consistent then the machine runs forever but ZFC cannot prove this. (It has been obvious practically since these concepts existed that such a Turing machine exists; the novelty is explicitly constructing a relatively small one.)
So yes, not all arithmetical sets are captured by ZFC. Godel’s Theorem says this will be the case for any effectively axiomatizable system that has as much arithmetical heft as Robinson arithmetic.