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

learn more… | top users | synonyms (1)

5
votes
3answers
320 views

Numbers which are “Provably Difficult to Compute”?

We recall that a computable number $\alpha \in \mathbb{R}$ satisfies the following: there exists a computable function $f$ such that, given any positive rational error bound, $f$ outputs a rational ...
3
votes
1answer
311 views

Size bound on regular expression describing language of an $n$-state deterministic automaton

The class of languages that can be recognised by some deterministic finite automaton is the same as those described by some regular expression. I evoked this well-known fact in class when discussing ...
0
votes
1answer
83 views

how can we categorize m-complete languages of RE (recursive enumerable, re-complete)?

is there any hierarchy for many-one complete languages of re (re-complete languages)? how can we propose a categorization for these languages? depending on what measures?
0
votes
1answer
248 views

Determining the density of roots to an infinite polynomial

Consider a polynomial defined by its roots: \begin{equation} P(z; \mathbf{S}) = \Pi_{\theta_j \in \mathbf{S}} (z - \exp({2 \pi i \theta_j}) ) \end{equation} where $\mathbf{S}$ is a set of numbers. ...
4
votes
3answers
416 views

A question on context-free languages from Sipser's computation book

I'm trying to learn some computability theory, and I came across a question in Sipser's book that I can't figure out. The exercise asks to show that there is an algorithm which will accept a ...
6
votes
2answers
487 views

RACs can solve the halting problem?

I was reading something which said: Less conventional is the Rapidly Accelerating Computer (RAC) whose clock accelerates exponentially fast, with pulses at (say) times $1-2^{-n}$ as n tends to ...
3
votes
1answer
178 views

Non-universal Turing machines

Is it possible to have two (or more) non-universal Turing machines labeled $A_1$ and $A_2$, such that if $f(A_i)$ is the set of functions computable by $A_i$, and S={every computable function} then ...
3
votes
2answers
155 views

Constructing a TM from a grammatically computable function

I have a grammatically computable function $f$, which means that a grammar $G = (V,\Sigma,P,S)$ exists, so that $SwS \rightarrow v \iff v = f(w)$. Now I have to show that, given a grammatically ...
9
votes
5answers
1k views

Example of a number that is not the limit of a computable sequence

Let's define a real number as computable iff there's an algorithm that can generate a sequence with the number as its limit (turing machine or any of the equivalent programming models). Not all real ...
17
votes
3answers
880 views

Is the Collatz conjecture in $\Sigma_1 / \Pi_1$?

Prompted by some of the comments on this question, I'm wondering if anything is known about the place of the Collatz Conjecture in the arithmetic hierarchy. More specifically, is Collatz known to be ...
2
votes
1answer
514 views

Finding General Expression from recursion

I am trying to find a general expression from a recursion. Here it goes: $(x+i)P_i = (i+1)P_{i+1} + \frac{x}{2} P_{i-1}$ $i$ goes from $0$ to $S$. How can I calculate a generic $P_i$ in terms of ...
-3
votes
2answers
101 views

Composition of a system with desired properties

Given the sets $K_1=\{\{a_0,b_1\},\{a_1\},\{b_0\}\}$. $K_2=\{\{c_1,c_0,d_0,e_1\},\{d_1\},\{e_0\}\}$ $K_3=\{\{f_0,f_2,g_0,h_1\},\{f_1,f_3,g_2,h_3\},\{b_1\},\{b_3\},\{c_0\},\{c_2\}\}$ Every item of ...
2
votes
2answers
207 views

Is there constructive proof of the fact that every recursive set $A \ne \varnothing$ is recursively enumerable in non-decreasing order?

Every proof I've read about this fact considers two cases: $A$ - finite and $A$ - infinite but this is undecidable. So, is there constructive proof?
1
vote
0answers
83 views

What would an “algebraic axiomatization of the partial recursive functions” be?

Hartley Rogers in his "Theory of recursive functions and effective computability" (page 55 in the first edition) writes "What resemblance types are also isomorphism types? A final answer to this ...
1
vote
2answers
255 views

Is Turing completeness monotone with respect to Cook reductions?

I think the post title is relatively clear assuming I worded it correctly, but since I was thinking of a specific example: The language of Boolean expressions is Turing complete; Does this imply that ...
3
votes
1answer
525 views

is a semirecursive (recursively semidecidable) set enumerable?

I'm getting confused. According to Computability and Logic fifth edition, semirecursive = recursively semidecidable, and according to wikipedia http://en.wikipedia.org/wiki/Recursive_set , ...
9
votes
1answer
456 views

Irrationality measure of the Chaitin's constant $\Omega$

What is known about irrationality measure of the Chaitin's constant $\Omega$? Is it finite? Can it be a computable number? Can it be $2$?
2
votes
2answers
292 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 ...
1
vote
1answer
173 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 ...
3
votes
1answer
127 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 ...
2
votes
1answer
174 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 ...
1
vote
0answers
49 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 ...
10
votes
1answer
200 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 ...
13
votes
5answers
4k 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 ...
3
votes
2answers
104 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?
4
votes
2answers
330 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}$. ...
1
vote
3answers
143 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 ...
1
vote
2answers
279 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$ ...
0
votes
2answers
300 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 ...
3
votes
1answer
346 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, ...
3
votes
3answers
5k 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 ...
17
votes
2answers
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 ...
7
votes
2answers
226 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 ...
1
vote
2answers
148 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 ...
19
votes
4answers
2k 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 ...
3
votes
2answers
154 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 ...
2
votes
1answer
91 views

Puzzle: Generate the Highest Bounded Number Using a Limited Number of Characters

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 ...
2
votes
1answer
93 views

One-reducibility extending to onto function

I'm working on the following problem from Soare: If $A$ is one-reducible to $B$ ($A \leq_1 B$) and $A, B$ c.e., $A$ infinite then $A$ is one-reducible to $B$ via some $f$ such that $f(A)=B$. I know ...
2
votes
1answer
140 views

Sipser's definition of a space constructable function

I have a problem with definition of space constructable function. As I understood we use this definition just for simplification of further proofs and idea behind this definition is very clear, but ...
2
votes
1answer
122 views

Looking for Wald Theorem

From the paper "What is a Random Sequence?" by Sergio B. Volchan, Math. Monthly 109, january 2002 Definition 3.1 An infinite binary sequence $x=x_1 x_2 \dots$ is random if it is collective; i.e., ...
4
votes
3answers
516 views

Proving that $\{x|\varphi_x \; \text{is extendible to a total computable function} \} \neq \omega$

The problem that I'm working on is to prove that $$ Ext=\{ x \ | \ \varphi_x \text{is extendible to a total computable function}\} $$ is not equal to $\omega$. Here $\varphi_x$ is the $x$-th partial ...
2
votes
2answers
147 views

Undecidable countable structure built on decidable relation?

My question is, is there a relation $R$ on the integers that's decidable (i.e. the function ${\mathbb Z}^2 \to \lbrace \text{true},\text{false} \rbrace, \ (i,j) \mapsto i R j$ is computable) , but ...
6
votes
7answers
778 views

Is there at least one irrational number with the property that it cannot be defined by a finite string of information?

Ok, so maybe that wasn't the best way of phrasing the question, but I think it's specific enough. Let me explain myself a bit more below in case I am wrong. So I'm assuming (although I've never ...
2
votes
0answers
230 views

Further question on “uncountable” Turing Machine

Having read An "uncountable" Turing Machine? I have further questions that I don't believe it addressed. (I'm a programmer, not a mathematician so I apologize if this is stupid or the ...
6
votes
3answers
337 views

Is the set of all deducible formulas decidable?

Consider any standard, "sufficiently expressive" first-order theory (say, $ZFC$ or Peano arithmetic) so that all the usual arithmetization and incompleteness results hold. The set $D$ of deducible ...
3
votes
3answers
542 views

Placing some sets in the arithmetic hierarchy

I'm working on the following problem: let $W_e$ be the computably enumerable set which is the domain of the $e$-th Turing program, and $K$ be the Halting problem, at which level of the arithmetic ...
3
votes
1answer
418 views

Understanding of pumping lemma

It seems like I missed something in pumping lemma. Please, help me out Let's take the simple example from Sipser's book Prove that language $L = \{0^n1^n | n>=0 \}$ is nonregular. Following the ...
26
votes
5answers
4k views

Are some real numbers “uncomputable”?

Is there an algorithm to calculate any real number. I mean given $a \in \mathbb{R}$ is there an algorithm to calculate $a$ at any degree of accuracy ? I read somewhere (I cannot find the paper) that ...
1
vote
3answers
284 views

Cardinality of the recursive subsets of the naturals

What is the cardinality of the set of recursive subsets of natural numbers?
3
votes
3answers
935 views

Is the language of all strings over the alphabet “a,b,c” with the same number of substrings “ab” & “ba” regular?

Is the language of all strings over the alphabet "a,b,c" with the same number of substrings "ab" & "ba" regular? I believe the answer is NO, but it is hard to make a formal demonstration of it, ...