Throughout the question ITTM refers to Hamkins' infinite Turing machines, though I will be interested in results related to stronger models.


Recently I was wondering, is it consistent that there is an ITTM which recognizes a set of reals which is not Lebesgue measurable? Here with "recognizable" I mean that the set has a form $\{r:$M halts on $r\}$ for some ITTM M. 


It is consistent (relative to an inaccessible) that there are no non-measurable sets, so it's consistent that every recognizable set is measurable.


Very similar questions can be asked about sets with Baire or perfect set properties. I have tried to find something about complexity of measurable sets that could resolve this, but I couldn't find anything. 


Thanks in advance. 



Can ITTM recognize a non-measurable set?
Nice question!


The answer is no, because if a set of reals $A$ is infinite time semi-decidable, then it is $\Delta^1\_2$, and not only $\Delta^1\_2$, but *absolutely* $\Delta^1\_2$, in the sense that the equivalent $\Sigma^1\_2$ and $\Pi^1\_2$ characterizations continue to be equivalent in all forcing extensions. This can be seen by using the fact that every infinite time computation either halts in some countable ordinal number of steps or repeats (in the suitably strong sense of repeating that we mention in the main paper on ITTMs). That is, for the $\Sigma^1\_2$ side, a real $x$ is in $A$ just in case there is a well-founded computation according to program $p$ accepting $x$; and for the $\Pi^1\_2$ side, $x$ is not in $A$ just in case there is a well-founded computation according to program $p$ that either rejects $x$ or else is strongly repeating. But it is an [old result of Bob Solovay](http://www.cs.nyu.edu/pipermail/fom/2008-April/012792.html) (see Kanamori exercise 14.4) that every absolutely $\Delta^1\_2$ set of reals is Lebesgue measurable. 


This argument appears in my joint article:


* Sam Coskey, Joel David Hamkins, [Infinite time decidable equivalence relation theory](http://jdh.hamkins.org/infinitetimecomputableequivalencerelations/), Notre Dame Journal of Formal Logic, vol. 52, iss. 2, pp. 203-228, 2011.


In that article, Sam and I undertake to develop the analogue of Borel equivalence relation theory, but using infinite time computable reductions in place of Borel reductions. So it is a nice blend of descriptive set theory and infinitary computability. Along the way we prove the following, using essentially the same argument I gave above. 


**Theorem 2.6** Every infinite time eventually computable function is absolutely $\Delta^1\_2$. 


**Corollary 2.7** Every infinite time eventually decidable set is measurable. Every infinite time eventually computable function is a measurable function.


Note that *eventually* decidable is a weaker property than semi-decidable, but there are some subtle issues with partial functions, as mentioned in the article. 


