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)

2
votes
2answers
320 views

For a Turing machine and input $w$- Is “Does M stop or visit the same configuration twice” a decidable question?

I have the following question out of an old exam that I'm solving: ...
2
votes
4answers
890 views

Halting problem on finite set of programs

As I understand the halting problem, it imply the fact that there doesn't exist one program which can answer the halting problem for every computable program and it rely on Cantor diagonalization to ...
2
votes
2answers
129 views

Solovay Randomness

Say that an $x\in 2^{\omega}$ is Solovay random if for all computably enumerable collections of intervals $\{I_n\}$ such that $\sum_n\mu(I_n)<\infty$, then $x\in I_n$ for at most finitely many $n$. ...
3
votes
1answer
353 views

Proving Turing Completeness by Simulating Rule 110

Something I've heard often is that Rule 110 is the `simplest' Turing-complete formalism. As a programming exercise in a language I am new to, I implemented a function that computes from an initial ...
2
votes
2answers
279 views

Why is the following language decidable? $L_{one\ right\ and\ never\ stops}$

I can't understand how the following language can ever be decidable: $L= \{ \langle M \rangle | M \ is \ a \ TM \ and\ there\ exists\ an\ input\ that\ in\ the\ computation\ $ $of\ M(w)\ the\ head\ ...
5
votes
1answer
197 views

The print problem: How to show it is not decidable?

I wonder the following reduction is correct. I'm trying to show that the following problem "PRINT_BLANK" is not decidable. Input: (a coding of) Turing machine M. Question: Does the machine never ...
1
vote
1answer
87 views

Showing that $\{0w:w \in A\} \cup \{1w: w \notin A \}$ computes $A$

I'm trying to construct a reduction from $A \in RE \setminus R$ under $\sum=\{0,1\}$ to $B$ which defined: $B=\{0w:w \in A\} \cup \{1w: w \notin A \}$. I need to show that $B\notin RE \cup co-RE$ ...
0
votes
1answer
114 views

For regular expression $E$ and a context free grammar $G$- why deciding if $L(G)\subseteq L(E)?$ is a recursive problem?

I'd love your help with understanding why does the following language is recursive: Input: a regular expression $E$ and a context free grammar $G$ question: $L(G)\subseteq L(E)?$ I tried to think ...
4
votes
1answer
139 views

An Obsessive Turing machine problem

Can you please help me understand whether or not the following the problem is recursive, recursively enumerable, or co-recursively enumerable? A Turing machine $M$ is said to be obsessive if on every ...
4
votes
1answer
151 views

Are there larger than countable chains in the join-semilattice of Turing degrees?

Recall that Turing degrees are equivalence classes of subsets of $\mathbb{N}$ under Turing equivalence (mutual Turing reducibility). They are partially ordered by Turing reducibility and form a join-...
8
votes
1answer
273 views

Does there exist a universal pushdown automaton?

Let $\Sigma$ be a fixed alphabet and let $PDA(\Sigma)$ be the set of all Push-Down-Automata (PDA's) having input alphabet $\Sigma$. Is there an alphabet $S$ and a function $f:PDA(\Sigma) \to S^∗$ such ...
2
votes
1answer
162 views

Is the set of codes of Deterministic Finite-State Automata a regular language?

Let $\Sigma$ be a given alphabet. Is there a way to code up Deterministic Finite state Automata (DFA) over $\Sigma$ as strings of $\Sigma$ in such a way that the corresponding subset of $\Sigma^*$ is ...
2
votes
2answers
138 views

Complexity of subset relation on Borel Sets

Fix $A, B \in \mathbf{\Delta}_{1}^{1}$ (i.e. they're Borel). Is the statement $A \subseteq B$ generally only $\mathbf{\Pi}^{1}_{1}$ (at best)? Of course, it's $\mathbf{\Pi}^{1}_{1}$ via $\forall x[x \...
2
votes
2answers
151 views

Were PR functions considered to be the class of total recursive functions?

At some point of history, were the class of primitive recursive functions considered (or even conjectured) to be the class of total recursive functions? I think I faced this claim sometime ago, but ...
2
votes
3answers
232 views

Complexity of the computable entailment relation

The following definition comes from Richard Shore's 2010 paper 'Reverse Mathematics: The Playground of Logic'. Let $\varphi$ and $\psi$ be sentences in the language of second order arithmetic $\...
1
vote
1answer
72 views

Satisfiability problem for FOL[<,R]

Let FOL[<,R] be the fragment of first-order logic enriched with two relational symbols < and R and the first-order axioms that say: < is a strict partial order and R is an irreflexive and ...
4
votes
0answers
521 views

algorithm for solving diagonal quadratic equations over real or complex numbers

I found the following statement in the paper http://www.math.uni-bonn.de/~saxena/papers/cubic-forms.pdf (page 22, in the middle): For $\mathbb F\in\{\mathbb R, \mathbb C\}$ and $b, a_i\in\mathbb F$...
5
votes
1answer
328 views

Recursively enumerable languages are closed under the min(L) operation?

Define $\min(L)$, an operation over a language, as follows: $$ min(L) = \{ w \mid \nexists x \in L, y \in \Sigma^+ , w=xy \} $$ In words: all strings in language L that don't have a proper prefix in ...
3
votes
3answers
202 views

A non-arithmetical set?

A set is called arithmetical if it can be defined by a first-order formula in Peano arithmetic. I first encountered these sets when exploring the arithmetical hierarchy in the context of ...
11
votes
3answers
211 views

Must a function that 'preserves r.e.-ness' be computable itself?

Does there exist a non-recursive function (say, from naturals to naturals) such that the inverse of every r.e. set is r.e.? If yes, how to construct one? If no, how to prove that? Any References?
1
vote
1answer
517 views

Computable functions' set is countable

I have to prove that computable functions (by computable we mean recursive functions or functions calculated by a program with a register machine) are countable. Let $\mathcal{C}$ be the set of ...
0
votes
1answer
384 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
746 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 ...
7
votes
3answers
384 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
162 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 $X$...
11
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
784 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 functions ...
4
votes
3answers
787 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
112 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
147 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
174 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
163 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
182 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
148 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 \not=...
1
vote
1answer
286 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
122 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
231 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
166 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
148 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 $\operatorname{...
0
votes
1answer
47 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
2k 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 intensive....
1
vote
1answer
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 ...
0
votes
1answer
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....
2
votes
1answer
120 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 ...
14
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
803 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
123 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
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-...
2
votes
1answer
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: ...