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
1answer
131 views

On the Decision Problem for Two-variable First-Order Logic

I have a question concerning the model construction of the $\forall \forall \land \forall \exists$ - Scott sentence on page 6 in this paper: www.cs.rice.edu/~vardi/papers/basl96.ps.gz Why do we ...
4
votes
1answer
341 views

Show $f$ is primitive recursive, where $f(n) = 1$ if the decimal expansion of $\pi$ contains $n$ consecutive $5$'s

Let $f:\mathbb{N}\to\mathbb{N}$ be given by $f(n)=1$ if the decimal expansion of $\pi$ contains $n$ consecutive $5$'s, and $f(n)=0$ otherwise. How would you go about showing such a function is ...
3
votes
1answer
232 views

A qualitative, yet precise statement of Godel's incompleteness theorem?

I read online a statement to the effect that (I'm paraphrasing): Goedel's incompleteness theorem shows that we cannot even have a complete and consistent theory for the natural numbers. I am ...
3
votes
1answer
367 views

The emptiness problem for “lunatic” and “crazy” Turing machines

Crazy Turing Machine is the same as Turing machine with one stripe , except of the fact that after each ten steps the head jumps back to the beginning of the stripe. Lunatic Turing Machine is the ...
3
votes
1answer
228 views

Computable function and decidable sets: For a computable $g$ and decidable set $A$ , Does $g(A), g^{-1}(A)$ necessarily decidable?

I'm trying to solve the following exercise from an old exam: For a computable function $G: \mathbb{N} \to \mathbb{N} $, and a set of numbers $A$, we define $g^{-1}(A)=\{x|g(x) \in A\} $ and $g(A)=\{g(...
4
votes
3answers
270 views

Recursively enumerable set? Any hints?

I don't mean to be pulling answers out of you, but I'm stuck. Any advice on the right direction would be appreciated. I have the following set $X$ ={$n$ where $n$ is a number of a turing machine $M$ ...
2
votes
1answer
171 views

For a Turing machine $M$ can we decide whether there's an input which at $M(x)$ never moves left?

After Reading again the answer to this question and the answer to this question, I am wondering if the language $L=\{\langle M \rangle | M $is a Turing machine and $\exists$ input $x$ such that in $...
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
902 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
130 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
354 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
282 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
199 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
274 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
163 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
139 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
523 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
330 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
385 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
755 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
386 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
786 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
790 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
148 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
183 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
288 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
167 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 ...