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

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-...
457 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: ...
862 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 ...
410 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 ...
238 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 ...
122 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 ...
399 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 ...
666 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

265 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.
104 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 ...
321 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 ...
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?
249 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. ...
418 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-...
492 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 ...
180 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 ...
537 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 ...
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 ...
180 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 ...
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 ...
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 ...
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 ...
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?
### 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}$. ...
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 ...