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
271 views

A revisit to the question: Can total recursive functions be recursively enumerated?

There is not a clear answer in literature on the question: Can total computable functions be computable enumerated?, i.e., is a set of encodings of total computable functions computably enumerable ...
2
votes
1answer
105 views

A question on essentially undecidable first-order theories

I am trying to show the following equivalence: a (consistent) first-order theory $T$ is essentially undecidable if and only if every complete extension of $T$ is undecidable. By "$T$ is essentially ...
13
votes
6answers
2k views

What philosophical consequence of Goedel's incompleteness theorems?

I want to write a philosophical essay centered about Goedel's incompleteness theorem. However I cannot find any real philosophical consequences that I can write more than half a page about. I read the ...
2
votes
2answers
599 views

Existence of recursively inseparable sets that are recursively enumerable

A set $A \subseteq \mathbb{N}$ is recursively enumerable if there exists a $\mu$-recursive function which enumerates it. Two sets $A, B \subseteq \mathbb{N}$ are recursively inseparable if there does ...
0
votes
1answer
116 views

Understanding of recursive functions

Computability is often defined in terms of recursive functions, recursively enumerable sets, recursive sets. Is the reason behind this – the following: a function that can be computed is a recursive ...
1
vote
0answers
185 views

Recurrence relation for the digits of the integer square root in binary

I was investigating a question on the Electrical Engineering Stack Exchange site, available here: ...
2
votes
1answer
367 views

Proving Recursive Functions are Representable in R

I am trying to prove that all recursive functions are representable in the theory $R$ whose language is $L$ and whose theorems are the consequences in $L$ of the following infinitely many sentences: ...
3
votes
1answer
627 views

Unpacking the Diagonal Lemma

I am studying from Boolos' Computability & Logic (3rd edition). I need help unpacking what the Diagonal Lemma states, and understanding its proof. The Diagonal lemma is formalized on page 105 from ...
1
vote
1answer
192 views

Formal statement of theorem about perfect numbers?

I cannot seem to find the formal statement of the theorem if there are infinite perfect numbers in Wikipedia or online. I searched this site but the closest is the generalization of perfect numbers ...
3
votes
1answer
308 views

Infinite finitely branching recursive tree with no path whose graph is $\Delta^0_2$

I am trying to construct an example of a infinite, finitely branching, recursive tree $T$ such that none of its paths has a graph which is $\Delta^0_2$. I denote the set of paths of $T$ by $[T]$. I ...
5
votes
1answer
225 views

How to compute isomorphism $V \simeq V^{**}$ (in Haskell)?

Since there is a canonical isomorphism between vector space $V$ and his dual dual space $V^{**}$, $\dim V \in \mathbb N \;$, I want to write it as a Haskell function. This function is going to have a ...
2
votes
0answers
113 views

constructive ordinal and $\Delta^1_1$ predicate

Everything I know on this subject comes from Sacks book : "Higher recursion theory" Let $\mathcal{O^Y}$ be the set of codes for ordinals constructive in $Y$. We should have the result that $A ...
3
votes
1answer
98 views

combinatory basis for head reduction

Consider combinatory calculi that don't have tail reduction. So there may be combinators $x$, $y$ and $z$ such that $y\to z$ but $xy\nrightarrow xz$. We can still write every combinator as a ...
1
vote
2answers
67 views

Effective complexity of $\leq_T$

Remember that we say for $\alpha,\beta$ in $\omega^\omega$, that $\alpha\leq_T \beta$ if $\alpha$ is recursive in $\beta$. Is $\leq_T$ a $\Sigma^1_1$ set, as a subset of $\omega^\omega\times ...
2
votes
2answers
110 views

Proving the free occurrence of a variable is primitive recursive

Show that FreeOcc$(m,n,i)$, which holds when $m$ is the godel number of a wff $\varphi$ and the $i^{th}$ symbol of $\varphi$ is a free occurrence of the variable $x_{n}$, is primitive recursive. ...
5
votes
2answers
109 views

Example of sets $A, B$ such that $A', B'$ are Turing equivalent but $A, B$ are not.

I have been wondering if the following statement is true, $$ A\equiv_TB\iff A'\equiv_TB' $$ where $A, B\subseteq\omega$ and $A'$ denotes the Turing jump of $A$. I have been able to show ...
2
votes
2answers
349 views

the set of sentences (i.e. closed formulas) of first-order logic and the Chomsky hierarchy

The set of well-formed formulas (wffs) in first-order logic (FOL) is decidable, because it's straightforward to translate the standard recursive syntax rules into a context free grammar, and all ...
4
votes
2answers
522 views

Non-recursive subset which is recursively enumerable

What is an example of recursively enumerable subset of the natural numbers which is not recursive?
2
votes
3answers
177 views

“direct” ways in which a non-computable number is used?

I was wondering whether non-computable numbers are ever of "direct" use ? I understand they are immensely useful indirectly, because we need them to do analysis in the real numbers for instance. ...
2
votes
2answers
112 views

Showing a set $\Sigma^0_n$ subset of $\mathbb{N}$ is $\Sigma^0_n$-complete

This is both a general and specific question in basic computability theory. Broadly speaking, I am not very comfortable with showing whether or not a subset of $\mathbb{N}$ is $\Sigma^0_n$ (or ...
1
vote
1answer
119 views

Relationship between $\Sigma_{1}$ and $\Pi_{1}$ functions (Logic)

I am working on the following homework problem for a logic class on Godel's incompleteness theorems and the following question is asked. Is the converse of Theorem $13.1$ true? Explain. Theorem ...
2
votes
1answer
176 views

Help on two exercises about computability theory

In Cooper's book, I can't think out the solutions of two exercises. 1.show that there exists a simple set S contains the set of all even numbers. 2.show that each creative set is contained in some ...
8
votes
2answers
2k views

Are total recursive functions recursively enumerable?

In quite some literature I found that primitive recursive functions are recursively enumerable (r.e.), but total recursive ones are not. Then, what set do they belong to? I am asking since I learned ...
3
votes
1answer
151 views

Why do $\omega$-models of subsystems of $\mathsf{Z}_2$ satisfy full induction?

Richard Shore, in his 2010 paper in the Bulletin of Symbolic Logic, 'Reverse Mathematics: The Playground of Logic', writes that Obviously, if an $\omega$-model $\mathcal{M}$ (those with $M = ...
2
votes
1answer
222 views

Halting problem and universality

Sorry this might be a layman question, but I could not find any information on this. Is the fact that there exists no Turing machine that can solve the halting problem equivalent to the existence of ...
3
votes
2answers
184 views

Are some numbers more computable than others?

As I understand it (layman alert), the definition of computable numbers is binary: either a number is or is not computable. Is it meaningful to imagine a function telling how computable (or ...
1
vote
2answers
146 views

Is Entscheidungsproblem in Co-RE? And Proof if it is.

As I study through, I learned that Entscheidungsproblem has a negative answer. Then I came to wonder whether the problem is in Co-RE. If it is, can anyone show me the proof? Thanks.
5
votes
2answers
96 views

Can we implement $\omega^{CK}_1$ using $\omega^{CK}_1+1$ as an oracle?

Let $\omega^{CK}_1$ denote the least non-recursive ordinal. Suppose we have an unknown well-ordering of $\mathbb{N}$ of the order type $\omega^{CK}_1+1$ as an oracle. Is it possible to write an ...
5
votes
3answers
289 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 ...
2
votes
1answer
271 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
74 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
218 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
2answers
318 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 ...
4
votes
2answers
427 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
155 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
122 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 ...
8
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
815 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
446 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
177 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
80 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
217 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
398 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 , ...
8
votes
1answer
432 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
270 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
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
141 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 ...