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)

1
vote
1answer
160 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
121 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
142 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
46 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
191 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
3k 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
103 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
311 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
139 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 ...
2
votes
2answers
234 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
268 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
317 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
3k 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
204 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
147 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 ...
18
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
131 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
88 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
89 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
122 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
119 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., ...
3
votes
3answers
418 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
134 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
690 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
209 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
301 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
427 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
400 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 ...
23
votes
5answers
3k 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
237 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
799 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, ...
8
votes
1answer
669 views

Recognizing and Using Chaitin's Constant

As far as I understand, Chaitin's constant is the probability that a given universal Turing machine will halt on a random program. I understand that Chaitin's constant is not computable--if it were, ...
3
votes
1answer
220 views

Decidability of equality of CFL's

Following problem is decidable: Given a context-free grammar $G$, is $L(G) = \varnothing$? Following problem is undecidable: Given a context-free grammar $G$, is $L(G) = A^{\ast}$? Is there a ...
7
votes
3answers
1k views

Prove Gödel's incompleteness theorem using halting problem

How can you prove Gödel's incompleteness theorem from the halting problem? Is it really possible to prove the full theorem? If so, what are the differences between original proof and proof by ...
4
votes
4answers
435 views

How many cpus needed to check a 100 million digit prime number efficiently?

If I had access to potentially large number of CPUs and wanted to quickly check 100 million digit numbers for primality using a map-reduce architecture, how many CPUs would be necessary? Each of the ...
5
votes
2answers
396 views

Does every infinite $\Sigma^1_1$ set have an infinite $\Delta^1_1$ subset?

The question is exactly that in the title: Does every infinite $\Sigma^1_1$ set of natural numbers have an infinite $\Delta^1_1$ subset? Some background: The lower-level analog of this question, Does ...
1
vote
3answers
372 views

How is Kleene's T predicate defined?

What I don't understand is how to extract information from the number that encode the computation history. I know it's defined in Kleene's Introduction to Metamathematics. But what page? References ...
10
votes
2answers
2k views

Can someone explain the Y Combinator?

The Y combinator is a concept in functional programming, borrowed from the lambda calculus. It is a fixed-point combinator. A fixed point combinator $G$ is a higher-order function (a functional, in ...
3
votes
2answers
455 views

Algorithm to determine if a Diophantine Equation has an infinite number of solutions

In their paper , Marker and Slaman, proved the decidability of the the theory of the natural numbers with the quantifier "for all but finitely many", One can obviously encode the question of whether ...
2
votes
1answer
154 views

bijective projection N <-> algorithms

I thought I'd might be interesting to do some "automated algorithm/turing-automata finding" (I had the busy beaver in mind). I thought about trying many in a specific language (brainfuck or smallfuck) ...
4
votes
1answer
129 views

A technique for deciding satisfiability in fragments of first-order logic

By Goedels completeness theorem satisfiability in first-order logic is $\Pi_1$. So to obtain decidability in some fragment, it is enough to show that satisfiability is $\Sigma_1$ in this fragment. I ...
2
votes
1answer
168 views

If $f$ is primitive recursive (but not necessarily bijective) and $M$ primitive recursive, is $f(M)$ primitive recursive?

In this post I wondered, whether a language over a finite alphabet is “stable” with respect to primitive recursiveness, recursiveness and recursive enumerability under different enumerations of the ...
1
vote
2answers
275 views

What is the importance of mentioning —U? (Turing 1936)

I'm trying to get my head around page 252 of Turing's "On Computable Numbers [...]", specifically near the end of the page where he talks about -U (logical negation of U, the German blackletter U). ...
3
votes
1answer
1k views

Proof that the set of incompressible strings is undecidable

I would like to see a proof or a sketch of a proof that the set of incompressible strings is undecidable. Definition: Let x be a string, we say that x is c-compressible if K(x) $\leq$ |x|-c. If x is ...
2
votes
3answers
173 views

A notion of topology for computability

A topology on a space $X$ is defined as a subset of the power-set of X, that is closed under arbitrary unions, finite intersections and includes the empty set and the full space. Is anybody aware of ...
4
votes
2answers
468 views

An “uncountable” Turing Machine?

A proof of the insolubility of the halting problem is a diagonalization, which I'm sure most of you have seen. I am not very familiar with set theory, but it strikes me as similar to Cantor's proof of ...
3
votes
1answer
469 views

Questions about the proof that minimal Turing machines are not recursively enumerable & proof that Kolmogorov complexity is uncomputable

This thread can be broken up into two questions. First I am trying to understand the proof that $MIN_{TM}$ is not recursively enumerable. If M is a Turing machine, then we say that the length of ...
-3
votes
2answers
1k views

Example of function which is not computable

I am looking for a concrete example of a function $$f: N^k \rightarrow N$$ $$(n_1, n_2, \cdots n_k) \mapsto f(n_1, n_2, \cdots n_k)$$ which is not computable. Source: Computability, An introduction ...
3
votes
3answers
113 views

Why isn't it enough to enforce $w \in A \Rightarrow f(w) \in B$ before allowing a reduction from A to B?

From my textbook, I can see that A language A is mapping reducible to language B if there is a computable function such that for every $w$, $w \in A \Leftrightarrow f(w) \in B$. Now, what I fail to ...