Response time is used here to interpret choice in decision problems. I first establish that there is a close connection between short response time and choices that are clearly a mistake. I then investigate whether a correlation also exists between response time and behavior that is inconsistent with some standard theories of decision making. The lack of such a correlation could be interpreted to imply that such behavior does not reflect a mistake. It is also shown that a typology of slow and fast responders may, in some cases, be more useful than the standard typologies.

We show that the set of natural numbers has an exponential diophantine definition in the rationals. It follows that the corresponding decision problem is undecidable.

We prove that some fairly basic questions on automata reading infinite words depend on the models of the axiomatic system ZFC. It is known that there are only three possibilities for the cardinality of the complement of an ω-language \hbox{$L(\mathcal{A})$}L(𝒜) accepted by a Büchi 1-counter automaton \hbox{$\mathcal{A}$}𝒜. We prove the following surprising result: there exists a 1-counter Büchi automaton \hbox{$\mathcal{A}$}𝒜 such that the cardinality of the complement \hbox{$L(\mathcal{A})^-$}L(𝒜) −  of the ω-language \hbox{$L(\mathcal{A})$}L(𝒜) is not determined by ZFC: (1) There is a model V1 of ZFC in which \hbox{$L(\mathcal{A})^-$}L(𝒜) −  is countable. (2) There is a model V2 of ZFC in which \hbox{$L(\mathcal{A})^-$}L(𝒜) −  has cardinal 2ℵ0. (3) There is a model V3 of ZFC in which \hbox{$L(\mathcal{A})^-$}L(𝒜) −  has cardinal ℵ1 with ℵ0 < ℵ1 < 2ℵ0.

We prove a very similar result for the complement of an infinitary rational relation accepted by a 2-tape Büchi automaton ℬ. As a corollary, this proves that the continuum hypothesis may be not satisfied for complements of 1-counter ω-languages and for complements of infinitary rational relations accepted by 2-tape Büchi automata. We infer from the proof of the above results that basic decision problems about 1-counter ω-languages or infinitary rational relations are actually located at the third level of the analytical hierarchy. In particular, the problem to determine whether the complement of a 1-counter ω-language (respectively, infinitary rational relation) is countable is in Σ13\(Π12 ∪ Σ12). This is rather surprising if compared to the fact that it is decidable whether an infinitary rational relation is countable (respectively, uncountable).

We show that many classical decision problems about1-counter ω-languages, context free ω-languages, or infinitary rational relations, are Π½ -complete, hence located at the second level of the analytical hierarchy, and “highly undecidable”.In particular, the universalityproblem, the inclusion problem, the equivalence problem, the determinizability problem, the complementability problem, and theunambiguity problem are all Π½ -complete for context-free ω-languages or for infinitary rational relations. Topological and arithmetical properties of1-counter ω-languages, context free ω-languages, or infinitary rational relations, are also highly undecidable.These very surprising results provide the first examples of highly undecidable problems about the behaviour of verysimple finite machines like 1-counter automata or 2-tapeautomata.

In this paper, we study the continuity of rational functions realized by Büchi finite state transducers. It has been shown by Prieur that it can be decided whether such a function is continuous. We prove here that surprisingly, it cannot be decided whether such a function f has at least one point of continuity and that its continuity set C(f) cannot be computed. In the case of a synchronous rational function, we show that its continuity set is rational and that it can be computed. Furthermore we prove that any rational ${\bf \Pi}^0_2$-subset of Σω for some alphabet Σ is the continuity set C(f) of an ω-rational synchronous function f defined on Σω.