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)

1
vote
2answers
218 views

Solving an equation in modular arithmetic

Given $A, B, C$ positive integers, $B < C,$ I would like some thoughts about (possibly efficient) ways to find the smallest integer $X$, where $0 < X < C$, such that: $$A X + B \pmod{C - ...
2
votes
2answers
520 views

How to solve this recurrence relation: $T(n) = 4\cdot T(\sqrt{n}) + n$

I was trying to solve this recurrence $T(n) = 4T(\sqrt{n}) + n$. Here $n$ is a power of $2$. I had try to solve like this: So the question now is how deep the recursion tree is. Well, that is ...
0
votes
1answer
47 views

Is a statement concerning the future part of a decidable problem?

Let Did I ever get 100% in an exam? be a problem and the corresponding (characteristic) function $$\chi(x)=\begin{cases}1,& \text{if the statement can be answered with ...
2
votes
2answers
576 views

Primitive recursive definition of the “divisibility” relation

Let $$d(x,y)= \begin{cases} 1, &\text{if }x\text{ is divisible by }y \\ 0, &\text{otherwise.} \end{cases}$$ How can I define $d(x,y)$ in terms of just the basic primitive recursive functions ...
1
vote
2answers
62 views

What is this number $k$?

I'm reading A first Course on Logic, (Hedman). An algorithm is said to be polynomial-time if there is some number $k$ so that, given any input of size n, the algorithm reaches it's conclusion ...
1
vote
1answer
1k views

Language that is recursively enumerable, but not recursive

I have a problem with this task: Show that this language is recursive enumerable, but not recursive: $L = \{ w \in \{0,1\}^* | M_w(x)\; \text{converges for some input}\; x \}$ (where $M$ is turing ...
6
votes
1answer
131 views

Terminal Paths in Kleene's O

I'm stuck on a problem in Sack's Higher Recursion Theory (#2.4)- any hints are welcome. He defines Kleene's O in the usual way, and the corresponding order $<_O$. A path through O is a linearly ...
0
votes
1answer
68 views

Why must language $L$ be decideable?

I am trying to teach myself computability theory with a textbook. According to my book, a function $f$ over an alphabet $A=\{a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, ...
0
votes
1answer
94 views

Why is not language $L=\{w_i \mid w_{2i} \notin M_i\}$ recursively enumerable?

Why is not language $$L=\{w_i \mid w_{2i} \notin M_i\}$$ recursively enumerable? I need to show that by diagonalization, but dont know how? Its quite obvious for $L=\{w_i \mid w_i \notin M_i\}$, but ...
8
votes
3answers
594 views

Does the recursion theorem give quines?

Wikipedia claims that the recursion theorem guarantees that quines (i.e. programs that output their own source code) exist in any (Turing complete) programming language. This seems to imply that one ...
16
votes
3answers
599 views

How can Busy beaver($10 \uparrow \uparrow 10$) have no provable upper bound?

This wikipedia article claims that the number of steps for a $10 \uparrow \uparrow 10$ state (halting) Turing Machine to halt has no provable upper bound: "... in the context of ordinary ...
5
votes
3answers
300 views

From lightface $\Sigma^1_1$ to boldface $\mathbf\Delta^1_1$

Fix some standard Polish space, e.g. Baire's space. It's a simple observation that every $\Delta^1_1$ is also $\mathbf\Delta^1_1$. It is the same observation that $\Sigma^1_1$ becomes ...
0
votes
1answer
48 views

Define the Complement of Factoring?

I just need some clarification as to what this terminology means in this situation. A decision problem for $FACTORING$ is as follows. INPUT: an integer $n$ and a integer $d$ QUESTION: does $n$ have a ...
2
votes
0answers
116 views

Unsolvability Degree in Turing's Proof 1

I have read that there is some debate over the exact origin of the Halting argument, which begins with Kleene and Davis in the 1950s [Copeland 2004]. Motivated by this I want to clarify the Degree of ...
-1
votes
1answer
140 views

Unbounded number of tapes of Turing Machine

Turing Machine with multiple tapes can be encoded such that its computational power is equivalent to Turing Machine with single tape. My question is if we have unbounded number of tapes, just like the ...
3
votes
1answer
177 views

Limits of Computable sequences

Turing introduced the fact that the limit of a computable sequence is not necessarily computable, and the Specker sequence is a specific example of such a number (with supremum not computable). My ...
4
votes
4answers
417 views

Examples of partial functions outside recursive function theory?

My math background is very narrow. I've mostly read logic, recursive function theory, and set theory. In recursive function theory one studies partial functions on the set of natural numbers. Are ...
2
votes
1answer
109 views

Showing a set of true sentences is recursive

Let's assume we are working in $(\mathbb{N}, +, \dot\ , 0,1)$. Let $T$ be a set of formulae that is closed under $\neg$ and such that the set of Godel numbers of formulae in $T$ is recursive. ...
11
votes
2answers
192 views

How does Borelness overlap with definability, computability, or constructiveness?

Background: I am writing a short paper aimed at math undergrads and focused as narrowly as possible on Borel equivalence relations. So, e.g., I am not assuming familiarity with recursion theory and am ...
5
votes
3answers
445 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
213 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
115 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
214 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
304 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
200 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
238 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
666 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
120 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
304 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
134 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
121 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
233 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
156 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
143 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
70 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
411 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
266 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
179 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
206 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
398 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 ...