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 ...
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 ...
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 ...
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 ...
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 ...
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$ ...