Questions about Turing computability and recursion theory, including the halting problem and other unsolvable problems. Questions about the resources required to solving particular problems should be tagged (computational-complexity).

learn more… | top users | synonyms (1)

2
votes
1answer
182 views

Hint on Kleene's O

I figured out this order on $\omega^2$: elements of different columns are ordered by their column number; within column $m$, the order is $0 \gt 1 \gt 2 \gt \cdots \gt n$, where $n$ is the first such ...
4
votes
1answer
256 views

(Semi-)Decidability of Turing-completeness of cellular automata

This is a follow-up to the question Undecidability in Conway’s Game of Life I posted at mathoverflow. For some cellular automata it can be proven that they can simulate a Turing machine, normally by ...
2
votes
2answers
248 views

Does this proof for the undecidability of the halting problem violate the axiom of regularity?

One proof of the halting problem goes by contradiction like this : Assume there is a Turing machine $H$ that can decide the halting problem, then construct a Turing machine $Q$ that takes as input a ...
12
votes
7answers
1k views

“Proof” that ZFC is inconsistent using Turing machines

I came across the following "proof" for the inconsistency of ZFC and can't find the flaw in it (if there is one...): Construct a Turing machine A which sequentially runs on all proofs in ZFC and ...
7
votes
4answers
374 views

Are the computable reals finitary?

In the comment thread of an answer, I said: The computable numbers are based on the intuitionistic continuum, and are not finitary. To which T.. replied: Computable numbers are not based on ...
7
votes
3answers
465 views

Why are $\Delta_1$ sentences of arithmetic called recursive?

The arithmetic hierarchy defines the $\Pi_1$ formulae of arithmetic to be formulae that are provably equivalent to a formula in prenex normal form that only has universal quantifiers, and $\Sigma_1$ ...