Questions tagged [turing-machines]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
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....
schnitzi's user avatar
  • 463
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(...
Milo Moses's user avatar
  • 2,779
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 ...
Sam Forster's user avatar
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 ...
Zoorado's user avatar
  • 1,203
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....
manu fava's user avatar
  • 393
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, ...
i like math's user avatar
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 ...
JoshuaZ's user avatar
  • 6,080
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$. ...
Niconar's user avatar
  • 75
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,...
Per Alexandersson's user avatar
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)$ ...
Manlio's user avatar
  • 302
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" ...
Thomas Benjamin's user avatar
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 ...
exfret's user avatar
  • 479
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 "...
Robert Wegner's user avatar
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 ...
Aidan Rocke's user avatar
  • 3,807
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 ...
Paul Budnik's user avatar