Which of the following is/are undecidable?

Answer: The undecidable problems are the ones about language equality, regularity of the language, and accepting all strings. The time-bound property with 10^73 steps is decidable.

• Language equality of two Turing machines: Deciding whether two Turing machines accept exactly the same language is undecidable. This is a nontrivial semantic property of recursively enumerable languages, so Rice's theorem applies. Concretely, if we could decide equality we could decide the emptiness problem by comparing a given machine to a machine that accepts no strings, which is impossible.

• Regularity of the language of a Turing machine: Deciding whether the language recognized by a Turing machine is regular is undecidable. Regularity is a nontrivial property of the language (some TMs accept regular languages, some do not), so Rice's theorem implies undecidability.

• Universality (accepts all strings): Deciding whether a Turing machine accepts every string is undecidable. This is again a nontrivial language property to which Rice's theorem applies; equivalently, standard reductions show that universality for Turing machines is undecidable.

• Bounded-step property (takes more than 10^73 steps on every string): This property is decidable. Let N = 10^73. To determine whether there exists any input on which the machine halts within N steps, it suffices to simulate the machine for N steps on every input whose first N+1 cells can affect those N steps (there are finitely many such strings). If any of these finite simulations halts within N steps, the machine does not take more than N steps on every input; otherwise it does. Therefore a finite algorithm decides the property.