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)

5
votes
3answers
439 views

What does the concept of computation actually mean?

My question is very general, and the kind of answer I look for would be as low level as it could be. I think I may illustrate my query more succinctly with an example. In propositional logic, you ...
1
vote
2answers
212 views

Primitive recursive functions and mutual recursion

Let $g$ and $g'$ be primitive recursive, of arity 2, and let $a,a'\in\mathbb{N}$. Define $f$ and $f'$ by the following formulae: $f(0)=a$ $f'(0)=a'$ $f(n+1)=g(n,f'(n))$ $f'(n+1)=g'(n,f(n))$. How ...
0
votes
2answers
105 views

Total function and termination

If we have a total function, is it by default terminating function? How can we prove the termination for this total function?
2
votes
1answer
113 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
294 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 ...
2
votes
1answer
212 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
302 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
198 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 ...
4
votes
3answers
239 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
136 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
237 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
653 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
118 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
299 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
229 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
173 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
74 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
109 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
132 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
114 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 ...
7
votes
1answer
231 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
155 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
133 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
142 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
226 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
69 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
398 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 ...
5
votes
1answer
263 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
178 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
205 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
392 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
321 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
577 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
289 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
147 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
593 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
616 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
132 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
170 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
101 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
199 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 ...