# Tagged Questions

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

166 views

### Solve equation on the PC

A friend of mine asked me to help him and make a small application to solve a problem. This problem can be reduced to this equation system: aX = Yb; Y > c; Y < d; X is a whole number (X has ...
342 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 (c....
121 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 ...
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 ...
805 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 ...
124 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 ...
230 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: http://electronics.stackexchange.com/questions/29311/calculating-the-square-root-of-8-bit-binary-...
463 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: ...
875 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 ...
202 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 ...
414 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 ...
239 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 ...
124 views

121 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. ...
113 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 ...
402 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 ...
670 views

### Non-recursive subset which is recursively enumerable

What is an example of recursively enumerable subset of the natural numbers which is not recursive?
190 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. ...
131 views

278 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 ...
193 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 ...
157 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.
105 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 ...
322 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 ...
312 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 ...
84 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?
253 views

### Determining the density of roots to an infinite polynomial

Consider a polynomial defined by its roots: $$P(z; \mathbf{S}) = \Pi_{\theta_j \in \mathbf{S}} (z - \exp({2 \pi i \theta_j}) )$$ where $\mathbf{S}$ is a set of numbers. ...
419 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 context-...
493 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 ...
181 views

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 ...
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?
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 ...
260 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 ...
543 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 , "...
457 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$?
293 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 ...
174 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 ...
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 ...