# Questions tagged [turing-machines]

The tag has no usage guidance.

8 questions
Filter by
Sorted by
Tagged with
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 ...
• 3,534
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$. ...
• 75
1 vote
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,...
• 14.8k
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)$ ...
• 192
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" ...
• 5,810
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 ...
• 449