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)

0
votes
1answer
323 views

Definition of effective enumerability and empty set

Let $S$ be a set. We say that $S$ is effectively enumerable iff (by definition) there exists a function $f \colon N \to N$ which has $S$ as codomain. My question is: is the empty set an effectively ...
9
votes
2answers
582 views

Why is it undecidable whether two finite-state transducers are equivalent?

According to the Wikipedia page on finite-state transducers, it is undecidable whether two finite-state transducers are equivalent. I find this result striking, since it is decidable whether two ...
6
votes
3answers
290 views

Reductions for regular languages?

To reason about whether a language is R, RE, or co-RE, we can use many-one reductions to show how the difficulty (R, RE, or co-RE-ness) of one language influences the difficulty of another. To reason ...
6
votes
2answers
148 views

Effective cardinality

Consider $X,Y \subseteq \mathbb{N}$. We say that $X \equiv Y$ iff there exists a bijection between $X$ and $Y$. We say that $X \equiv_c Y$ iff there exist a bijective computable function between ...
9
votes
3answers
2k views

Proving that the halting problem is undecidable without reductions or diagonalization?

I'm currently teaching a class on computability and recently covered the proof that the halting problem is undecidable. I know of three major proof avenues that can be used here: Diagonalization - ...
2
votes
3answers
601 views

Is the set of total recursive functions countable?

There are many reasons to hold that the set of total recursive functions is countable, and among them the two following seem to me to be very powerful and sound : The set of total recursive ...
3
votes
3answers
621 views

Primitive recursive functions, Recursive functions and recursive set

I'm trying to understand basic computability notions, and I'm a bit confused concerning the following questions : Is the set of (Gödel numbers of) partial recursive functions recursive ? Is the set of ...
0
votes
2answers
103 views

A problem that is Turing degree greater than $0'$ and not co-re

I know that halting problem is Turing degree $0'$. So, what degree would Co-RE complete problems be in? And is there any problem we can formulate (<- this might be too general, but let us say in ...
4
votes
1answer
136 views

expressiveness of computable infinitary logic

A language $L_{\omega_1\omega}$ generalizes an ordinary first-order language by allowing countably long disjunctions. If we take its nonlogical vocabulary to contain just a predicate for the ...
2
votes
2answers
164 views

Turing reduction

I'm learning algorithm theory. Homework question is: Are $A$ and $B$ possible so that $A\not\le_{tt}B$ (impossible to reduce using tt), but $A\le_T B$. But I can't think of any example..
4
votes
1answer
158 views

Projecting onto (lightface) Borel sets

Suppose $A \subseteq \omega^{\omega} \times \omega^{\omega}$ is Borel. If we project $A$ onto $\omega^\omega$, we get a $\mathbf{\Sigma^{1}_{1}}$ set $\{y: \exists x (y,x) \in A\}$. What if we project ...
2
votes
2answers
171 views

is the language of Turing machine encodings context-sensitive?

Say we have an encoding of the set of all Turing machines/Turing programs -- WLOG, let's say the encoding takes values in the binary numerals. Call this set of binary numerals that represent Turing ...
1
vote
2answers
137 views

Finding a total function not in a computable sequence of functions

Suppose $f(x,y)$ is a total computable function. For each $m$, let $g_m$ be the computable function given by $g_m(y) = f(m,y)$. Construct a total computable function h such that for each $m$, $h ...
1
vote
1answer
273 views

Equivalence of sequences and subsets of natural numbers

For me, facts like the independence of the continuum hypotheses from ZFC cast a doubt on the "law of the excluded middle". (In this context, the doubt is that there might be no "final set theory" such ...
0
votes
1answer
102 views

Creating ways to encode recursive function.

This is from an exercise in Boolos' Computability text. My problem is as follows: I am looking for a method that encode numbers for recursive functions. Then given such an encoding for recursive ...
0
votes
1answer
105 views

there is no partial recursive function f s.t. whenever N-W_e has one element, f converges and N-W_e = f(e)

question is as written in the title: show that there is no partial recursive function f s.t. whenever N-W_e has one element, f converges and N-W_e = {f(e)}. W_e is the domain of the program coded by ...
3
votes
1answer
203 views

Proof of a Theorem in Gao's 'Invariant Descriptive Set Theory'

Theorem 1.7.5 on p.35 of Gao's Invariant Descriptive Set Theory reads Theorem 1.7.5 (Kleene) If $A\subseteq X \times \omega^{\omega}$ is $\Pi^{1}_{1}$ and $$x \in B \Longleftrightarrow \exists y ...
4
votes
1answer
146 views

Notation in Sacks' 'Higher Recursion Theory'

I'm having trouble with the notation in Sacks' Higher Recursion Theory. I've asked specific questions from page 4. Instead of reading my question in detail and trying to understand my confusion (which ...
9
votes
2answers
143 views

A homogeneous set of some kind

Let $f : \mathbb{N}^k \to \mathbb{N}$ be a computable total function such that $f (\vec{x}) > \max \vec{x}$ for all $\vec{x}$. Question. Why is there a decidable set $A$ such that ...
0
votes
1answer
45 views

Boolean Expression

If the syntax of a language is: $a ::= n | x | a_1 + a_2 | a_1 \star a_2 | a_1 - a_2 $ $b ::= true | false | a_1 = a_2 | a_1 \leq a_2 | ¬ b | b_1 \wedge b_2 $ As $x_1 > x_2 $ is not permitted in ...
0
votes
1answer
1k views

Most computationally intensive algorithm.

I am trying to develop a benchmark to stress the CPUs on the Server for some HPC (High Performance computing) application. Please help me with some Algorithm that is believed to very CPU ...
1
vote
1answer
162 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 ...
1
vote
1answer
291 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
621 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
119 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
194 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
403 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
683 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
197 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
343 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
228 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
116 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
103 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
115 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
111 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
359 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
555 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
181 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
113 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
123 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
204 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
153 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
231 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
187 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
147 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
99 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 ...