# Questions tagged [turing-machines]

The turing-machines tag has no usage guidance.

8
questions

6
votes

1
answer

167
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

86
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

60
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,...

2
votes

1
answer

140
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

499
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

111
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 "...

3
votes

1
answer

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