# Tagged Questions

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

4k views

### What properties of busy beaver numbers are computable?

The busy beaver function $\text{BB}(n)$ describes the maximum number of steps that an $n$-state Turing machine can execute before it halts (assuming it halts at all). It is not a computable function ...
1k views

### Why do we believe the Church-Turing Thesis?

The Church-Turing Thesis, which says that the Turing Machine model is at least as powerful as any computer that can be built in practice, seems to be pretty unquestioningly accepted in my exposure to ...
4k views

### Are some real numbers “uncomputable”?

Is there an algorithm to calculate any real number. I mean given $a \in \mathbb{R}$ is there an algorithm to calculate $a$ at any degree of accuracy ? I read somewhere (I cannot find the paper) that ...
3k views

### There is a subset of positive integers which no computer program can print

It's said that a computer program "prints" a set A ($A \subset \mathbb N$, positive integers.) if it prints every element in A in ascending order (Even if A is infinite.). For example, the program can ...
3k views

### Example of uncomputable but definable number

Every computable number is definable. However, the converse is not true. What is an example of a real number that is definable but that is NOT computable? I guess if it is there, we can "define" (...
5k views

### Are there any examples of non-computable real numbers?

Is this true, that if we can describe any (real) number somehow, then it is computable? For example, $\pi$ is computable although it is irrational, i.e. endless decimal fraction. It was just a luck, ...
2k views

### Given any computable number, is there any algorithm to decide whether it is transcendental?

Given any computable number $a_c$, is there any algorithm to decide whether it is transcendental? Definition of “computable number”: According to Ming Li and Vitanyi, a real number $x=0.x_1x_2\ldots$ ...
2k views

### Are transcendental numbers computable?

Wikipedia states: "The computable numbers include many of the specific real numbers which appear in practice, including all real algebraic numbers, as well as e, π, and many other transcendental ...
3k views

### Is it possible to solve any Euclidean geometry problem using a computer?

By "problem", I mean a high-school type geometry problem. If no, is there other set of axioms that allows that? If yes, are there any software that does that? I did a search, but was not able to ...
2k views

### Is chess Turing-complete?

Is there a set of rules that translates any program into a configuration of finite pieces on an infinite board, such that if black and white plays only legal moves, the game ends in finite time iff ...
24k views

### Recognizable vs Decidable

What is difference between "recognizable" and "decidable" in context of Turing machines?
733 views

### How can Busy beaver($10 \uparrow \uparrow 10$) have no provable upper bound?

This wikipedia article claims that the number of steps for a $10 \uparrow \uparrow 10$ state (halting) Turing Machine to halt has no provable upper bound: "... in the context of ordinary ...
1k views

### How to interpret “computable real numbers are not countable, and are complete”?

On page 12 of this (controversial) polemic http://web.maths.unsw.edu.au/~norman/papers/SetTheory.pdf Wildberger claims that Even the "computable real numbers" are quite misunderstood. Most ...
2k views

### Density of halting Turing machines

If we enumerate all Turing machines, $T_1$, $T_2$, $T_3,\ldots,T_n,\ldots$, What is $$\lim_{m\to\infty}\frac{\#\{k\mid k\lt m \text{ and }T_k\text{ halts}\}}{m}\quad?$$ Or does this depend on how we ...
882 views

### Is the Collatz conjecture in $\Sigma_1 / \Pi_1$?

Prompted by some of the comments on this question, I'm wondering if anything is known about the place of the Collatz Conjecture in the arithmetic hierarchy. More specifically, is Collatz known to be ...
755 views

### Mathematical Notation and its importance

You can see how mathematical notation evolved during the last centuries here. I think everyone here knows that a bad notation can change an otherwise elementar problem into a difficult problem. Just ...
510 views

### Explicit automorphisms of the field of algebraic numbers

The field $\overline {\bf {Q}}$ of algebraic numbers admits many automorphisms other than conjugation. This follows from Galois theory: the field $\overline {\bf {Q}}$ can be realized as the union ...
215 views

### Tennenbaum's theorem without overspill

While trying to clean up Wikipedia's proof sketch for Tennenbaum's theorem (there is no computable non-standard model of Peano Arithmetic), the following strategy occurred to me. Since it seems to be ...
2k views

### What philosophical consequence of Goedel's incompleteness theorems?

I want to write a philosophical essay centered about Goedel's incompleteness theorem. However I cannot find any real philosophical consequences that I can write more than half a page about. I read the ...
324 views

### Primitive recursive function which isn't $\Delta_0$

What is the simplest/cutest example (and/or example with the most student-friendly proof that it is an example) of a primitive recursive function which isn't representable by a $\Delta_0$ wff?
4k views

### What is the fastest growing total computable function you can describe in a few lines?

What is the fastest growing total computable function you can describe in a few lines? Well, not necessarily the fastest - I just would like to know how far an ingenious mathematician can go using ...
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 ...
3k views

### Can someone explain the Y Combinator?

The Y combinator is a concept in functional programming, borrowed from the lambda calculus. It is a fixed-point combinator. A fixed point combinator $G$ is a higher-order function (a functional, in ...
127 views

### When is Chaitin's constant normal?

Chaitin's constant is not one constant, but depends on an effective prefix-free encoding $d$ of Turing machines as bit strings. Once such an encoding is chosen, the corresponding Chaitin's constant is ...
1k views

### What is undecidability

What does it mean that some problem is undecidable? For instance the halting problem. Does it mean that humans can never invent a new technique that always decides whether a turing machine will halt?...
248 views

### A result of van der Waerden says Galois theory “needs” incomputable sets - what does this mean, exactly?

I happened across the recent arXiv paper Transfinite Recursion In Higher Reverse Mathematics, and the introduction begins: The question "What role do incomputable sets play in mathematics?" has ...
197 views

### Consistency strength of Turing measurability

This is probably well-known to recursion theorists, but as google didn't help me, I'll ask it here. Convention: All sets of reals in the following discussion are assumed to be closed under Turing ...
211 views

### How does Borelness overlap with definability, computability, or constructiveness?

Background: I am writing a short paper aimed at math undergrads and focused as narrowly as possible on Borel equivalence relations. So, e.g., I am not assuming familiarity with recursion theory and am ...
2k views

### Proving that the halting problem is undecidable without reductions or diagonalization?

I'm currently teaching a class on computability and recently covered the proof that the halting problem is undecidable. I know of three major proof avenues that can be used here: Diagonalization - ...
172 views

356 views

### Countable choice and term extraction

The constructive Axiom of Countable Choice (ACC) is widely accepted due to its computational content. It states that:  \forall n\in \mathbb{N} . \exists x \in X . \varphi [n, x] \implies \exists f: ...
200 views

### Is there a dense subset of $\mathbb{R}^2$ with all distances being incommensurable?

Is there a set $S$ of points on the real plane $\mathbb{R}^2$ such that: there is a point belonging to $S$ in any neighborhood of every point of $\mathbb{R}^2$ (so, $S$ is dense) and ratio of any ...
237 views

### The ethics of Borel determinacy

I was speaking with a friend the other day, and I happened to say "morally, Borel determinacy is as strong as ZF." I was riffing on the well-known result of Harvey Friedman, that we need $\omega_1$-...
165 views

### Elementary references on Robinson Arithmetic, Prim. Recursive fns etc.

I'm in the middle of revising my freely available and much-downloaded introductory notes Gödel Without (Too Many) Tears. (They are a sort of cut down version of part of my Gödel book, and I'm ...
567 views

### A computer's memory is finite, so how can there be languages more powerful than regular?

A computer has a finite memory. There are no computers with infinite memory. Therefore the only languages that a computer can process are those whose member strings are finite. As I recall, the ...
1k views

### Show that the question “Is there life beyond earth?” is decidable

I was given a question to prove that there exists a turing machine that solves the question Is there life beyond earth? and is decidable. I actually don't understand how to show a turing ...
821 views

### Does the recursion theorem give quines?

Wikipedia claims that the recursion theorem guarantees that quines (i.e. programs that output their own source code) exist in any (Turing complete) programming language. This seems to imply that one ...
742 views

### Why is it undecidable whether two finite-state transducers are equivalent?

According to the Wikipedia page on finite-state transducers, it is undecidable whether two finite-state transducers are equivalent. I find this result striking, since it is decidable whether two ...
642 views

### Is the group isomorphism problem decidable for abelian groups?

According to wikipedia the group isomorphism problem is an undecidable problem. When we restrict to (countable) abelian groups does it become decidable or does it remain undecidable? In case it ...