# Questions tagged [turing-machines]

The turing-machines tag has no usage guidance.

15
questions

33
votes

3
answers

4k
views

### Using Busy Beavers to prove conjectures

I've been pondering some stuff on Shtetl Optimized where Yedidia and Aaronson construct Turing machines that will only halt if (e.g.) the Riemann Hypothesis is false, or Goldbach's conjecture is false....

12
votes

1
answer

3k
views

### Is there a "halting machine" which halts on itself?

The crux of the halting problem is that there can be no Turing machine $M$ such that $\text{Halt}(M(N))=\neg \text{Halt}(N(N))$ for all Turing machines $N$, since $\text{Halt}(M(M))=\neg \text{Halt}(M(...

4
votes

1
answer

214
views

### Can a halting oracle determine if a Turing machine is an ordinal?

For the sake of clarity, I am regarding a computable relation on $\mathbb{N}$ as a $2$-symbol ($0$ and $1$) Turing machine $T$ which halts on any initial binary string (which are interpreted as some ...

2
votes

3
answers

105
views

### If the join of two degrees compute one of their jumps, what can we say about the jump of the other degree?

Let $\mathbf{a}$ and $\mathbf{b}$ be two Turing degrees such that $\mathbf{a'} = \mathbf{a} \oplus \mathbf{b}$. Must it be the case that $\mathbf{a'} \leq \mathbf{b'}$? What if in addition, we know ...

27
votes

3
answers

3k
views

### "Natural" undecidable problems not reducible to the halting problem

There is a lot of known examples of undecidable problems, a large amount of them not directly related to turing machines or equivalent models of computations, for example here: https://en.m.wikipedia....

9
votes

2
answers

2k
views

### Why do almost all points in the unit interval have Kolmogorov complexity 1?

Re-posted from math.stackexchange as I did not get any answers there.
I am reading
Jin-yi Cai, Juris Hartmanis, On Hausdorff and topological dimensions of the Kolmogorov complexity of the real line, ...

6
votes

1
answer

229
views

### A variant of the Busy Beaver function

Set $BB(k,n)$ to be the same definition as the Busy Beaver but where one is looking at all $n$-state machines, and the transition graph has at most $k$ "write 1" instructions. This may be a ...

0
votes

1
answer

99
views

### Turing degrees inside the $\Pi_1^0$ class with top Medvedev degree

I'm sure i have read that the following (or something that implies this) is true
Let $X$ be a $\Pi_1^0$ class with top Medvedev degree. Then for every
$x\in X$, there is $y\in X$ with $y<_T x$.
...

1
vote

0
answers

96
views

### Game with Turing machines

Introduction
The following game is quite nice: Alice has, in secret, constructed a polynomial $P \in \mathbb{Z}[x]$.
On day $n=1,2,3,...$, she secretly writes down $P(n)$ on a piece of paper.
Each day,...

3
votes

1
answer

163
views

### Computing the halting problem with no computable bound on the use function

I would like to prove that there are two sets $A,B\subset \mathbb{N}$ such that
$A |_T B$
$\emptyset' \equiv_T A\oplus B$
for every $e$, if $\{e\}^{A\oplus B}=\emptyset'$ then the map sending $(B,n)$ ...

2
votes

2
answers

541
views

### Are ITTM's necessary to compute Turing's "computable numbers" and what does that mean for ordinary recursion theory?

In his celebrated paper, "On Computable Numbers, With An Application To the Entscheidungsproblem", Turing defines a "computable number" as follows:
The "computable" ...

26
votes

3
answers

3k
views

### What sorts of extra axioms might we add to ZFC to compute higher Busy Beaver numbers?

First, some context. Ever since I was a high schooler, I have been fascinated with large numbers. As I have grown in mathematical maturity, I have become both disappointed and fascinated to see that ...

2
votes

0
answers

122
views

### Is Steiner symmetrization "Turing complete"?

This question stems from intuition so it is a little soft. It concerns performing computation using transformations on sets. The idea is that a rearrangement like Steiner symmetrization might be "...

4
votes

1
answer

667
views

### Proof that dynamical systems with bounded Kolmogorov complexity can't emulate all Turing machines

Motivation:
During a discussion with neuroscientists the question arose as to whether the human brain may emulate any Turing machine. If we assume that animal brains may be modelled as deterministic ...

3
votes

1
answer

759
views

### Is there a well defined subset of the integers that cannot be defined as a property of a recursive process or Turing Machine?

Is there a well defined subset of the integers that cannot be defined as a property of a recursive process or Turing Machine?
I have long been intrigued by the observation that much of mathematics ...