Questions tagged [turing-machines]
The turing-machines tag has no usage guidance.
17 questions
5
votes
1
answer
386
views
Are directed graphs with out-degree exactly 2 strongly connected with probability 1?
Consider a directed graph with out-degree exactly two with $n$ vertices $v_1, v_2 \cdots v_n$ that is constructed as follows: For each vertex $v_i$, one chooses uniformly at random two (not ...
- 6,969
35
votes
3
answers
5k
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....
- 483
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(...
- 2,902
4
votes
1
answer
286
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 ...
- 700
2
votes
3
answers
122
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 ...
- 1,328
29
votes
3
answers
4k
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....
- 413
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, ...
- 297
6
votes
1
answer
279
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 ...
- 6,969
0
votes
1
answer
104
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$.
...
- 75
1
vote
0
answers
113
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,...
- 15.8k
3
votes
1
answer
170
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)$ ...
- 342
2
votes
2
answers
560
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" ...
- 6,132
28
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 ...
- 509
2
votes
0
answers
126
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 "...
- 203
4
votes
1
answer
678
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,871
35
votes
2
answers
7k
views
Is there a known Turing machine which halts if and only if the Collatz conjecture has a counterexample?
Some of the simplest and most interesting unproved conjectures in mathematics are Goldbach's conjecture, the Riemann hypothesis, and the Collatz conjecture.
Goldbach's conjecture asserts that every ...
- 1,173
3
votes
1
answer
786
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 ...
- 371