The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Questions tagged [computability]

Questions about Turing computability and recursion theory, including the halting problem and other unsolvable problems. Questions about the resources required to solving particular problems should be tagged (computational-complexity).

1,704 questions
Filter by
Sorted by
Tagged with
476 views

Definition of a computable (or recursive) set

I am new to computability theory, but I understand the usual definition of a "computable set" S when S is a subset of the natural numbers. Is there a notion of "computable set" that doesn't involve ...
231 views

Partial recursive functions as products of sets of total recursive functions?

Let C be a collection of two or more total recursive functions. Define ϕ(x) as the function which is undefined if any two members of C give different values for x as input, and whose output is the ...
138 views

The set of arithmetical numbers

Define $x\in\mathbb{R}$ to be arithmetical number if the set $\{\langle p, q \rangle \in \mathbb{Z}^2 : \frac{p}{q} < x\}$ is an arithmetical set. Define $x\in\mathbb{C}$ to be arithmetical number ...
270 views

Are there any R-complete problems?

Many complexity classes have complete problems. For example, NP has the NP-complete problems (using polynomial-time reductions), and RE has some RE-complete problems like the halting problem (using ...
55 views

Computability of “isomorphism existence” between special cubic number fields

Let $a$ be a rational number such that the polynomial $P_a=X^3-X-a$ is irreducible, let $\alpha_{a}$ denote a root of $P_a$ and let ${\mathbb K}_a={\mathbb Q}(\alpha_{a})$. Similarly, let $b$ be a ...
245 views

Is there a dense subset of $\mathbb{R}^2$ with all distances being incommensurable?

Is there a set $S$ of points on the real plane $\mathbb{R}^2$ such that: there is a point belonging to $S$ in any neighborhood of every point of $\mathbb{R}^2$ (so, $S$ is dense) and ratio of any ...
7k views

What is the fastest growing total computable function you can describe in a few lines?

What is the fastest growing total computable function you can describe in a few lines? Well, not necessarily the fastest - I just would like to know how far an ingenious mathematician can go using ...
109 views

Existence of a normal computable infinite pseudorandom sequence

Is there any computable infinite pseudorandom sequence of 0's and 1's which have been proven to be normal?
455 views

Does the $k$th forward difference of Radó's $\Sigma$ eventually dominate every computable function?

Let $\Sigma$ be Radó's Busy Beaver function, and let $\Delta[\Sigma]$ denote the forward difference of $\Sigma$, such that $\Delta[\Sigma] \ (n) = \Sigma(n+1) - \Sigma(n)$ for all $n \in \mathbb{N}$. ...
156 views

Does method exist to solve Diophantine/Algebraic equation with nearest integer variable?

Can anyone kindly tell me if there is a method (other than trial and error) to solve equations of the form below: $$x^2 + x - 35 - 35[(x^2)/35] = 0$$ where $x$ is an integer and $[y]$ denotes the ...
530 views

Can this version of the halting problem be solved?

I think the halting problem is not a result regarding computability, but rather expressiveness or restrictiveness. It's like asking a computer to prove $0=1$ or color a planar graph using only $3$ ...
381 views

Is an abstract machine Turing-complete if it can simulate itself?

For instance, in programming languages it's common to write an X-in-X compiler/interpreter, but on a more general level many known Turing-complete systems can simulate themselves in impressive ways (e....
406 views

Properties of computable numbers

If we enumerate* all the computable numbers, those for which there exist a turing machine that outputs its digits to arbitrary precision. What is known about the asymptotic density of rationals, ...
13k views

What is the difference between total recursive and primitive recursive functions

I am studying the theory of computation. Here are some terminologies that I am confused about. Are total recursive function and primitive recursive function equivalent? I think they are equal because ...
2k views

Density of halting Turing machines

If we enumerate all Turing machines, $T_1$, $T_2$, $T_3,\ldots,T_n,\ldots$, What is $$\lim_{m\to\infty}\frac{\#\{k\mid k\lt m \text{ and }T_k\text{ halts}\}}{m}\quad?$$ Or does this depend on how we ...
282 views

Complexity of the set of computable ordinals

According to http://en.wikipedia.org/wiki/Analytical_hierarchy The set of all natural numbers which are indices of computable ordinals is a $\Pi^1_1$ set which is not $\Sigma^1_1$. However, "the ...
167 views

Sequences of a computable function

Is there any computable function $f(n)$, which given any integer $n$ has been proven to return either $0$ or $1$ in finite time, and for which the statement "$f(1), f(2), f(3),\ldots$ contains ...
3k views

Is chess Turing-complete?

Is there a set of rules that translates any program into a configuration of finite pieces on an infinite board, such that if black and white plays only legal moves, the game ends in finite time iff ...
246 views

Upper and Lower bounds on proof length

Given a First Order language say, for arithmetic $\langle 0, 1, +,\cdot ,^\wedge, S \rangle$, Can one establish any lower or upper bounds on the length of proofs from certain recursively enumerable ...
A friend and I were sitting in our cubes at work and trying to create the greatest bounded number we could using only a few characters. We came up with $A(G,G)$, which is the Ackermann function with ...