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)

11
votes
2answers
523 views

Good introductory books on primitive recursive functions

I wondered if anyone could recommend any good introductory books on primitive recursive functions. I'm currently working through a Number Theory and Mathematical Logic module, and I'm finding it ...
6
votes
2answers
209 views

Ordinals definable over $L_\kappa$

Suppose $\kappa$ is an uncountable cardinal, with $L_\kappa$ an admissible set (i.e. a model of Kripke–Platek set theory). Let $<_\gamma \subseteq \kappa \times \kappa$ denote a wellordering of ...
2
votes
1answer
40 views

Prove there exists a recursive language which no TM accepts in n steps.

There is a problem I can't solve: Assume n is an integer. Prove that there exists a recursive language such that there is no Turing Machine which accepts it and makes a maximum of n steps for every ...
1
vote
1answer
91 views

Proving uncomputability — Rice's theorem

I am trying to prove the uncomputability of the following function: Let $\varphi$ be a Gödel-numbering of the computable functions. Consider the following function: \begin{align*} f(x) = \left\{ ...
3
votes
2answers
217 views

Primitive recursive select from parameters

I'm looking forward function, that works like that $\mathbb{N}^{n+1} \rightarrow \mathbb N$: $f(y, x_1, x_2, \dots ,x_n)=x_y$ We use projection $\Pi^n_k$, but I need something with "dynamic" size ...
5
votes
2answers
273 views

Is there a function that only generates primes?

The title sums it up: does there exist a "nice" injective function $f(n)$ such that $f(n)\in\mathbb P$ for all $n\in\mathbb N$? I'm having difficulty specifying exactly what I want "nice" to mean, ...
0
votes
2answers
104 views

Is the halting of a program that checks for duplicates in an infinite multiset decidable?

A program $P(\Sigma)$ takes input $\Sigma$, which is an nonempty multiset. Let $\Phi$ be an empty multiset. Take any element $\sigma$ from $\Sigma$. If $\sigma \in \Phi$, return true. Otherwise, ...
2
votes
1answer
94 views

IF a language L logspace reduces to SAT, does L

If a language L logspace reduces to SAT, does L also reduce to SAT in polynomial time?
1
vote
1answer
144 views

Show that K and complement to K are “1-reducible” to EQ={⟨x,y⟩|φx≃φy}

Where $K = \{x | φ_x(x) \downarrow\}$, $φ_x$ is a $\mu$-recursive function computing $M_x$, $M_x$ is Turing machine with Godel's number $x$. Set $A$ is "1-reducible" to set $B$ ($A \leq_1 B$) when ...
-1
votes
1answer
221 views

How to show if a function is partial recursive?

I have seen and understood the most definitions but i just could not understand how to show if a function is mu-partial recursive or not. I used search engines, but all I find are just more lectures ...
1
vote
1answer
175 views

The set of Turing machines that recognize $\{00, 01\}$ is undecidable

$L =\big\{\langle T\rangle \mid T\text{ is a Turing machine that recognizes }\{00, 01\}\big\}$. Prove $L$ is undecidable. I am really having difficulties even understanding the reduction to use ...
1
vote
2answers
326 views

The symmetric difference of two recursive (recursively enumerable) sets is recursive (recursively enumerable)

I want to prove it, but don't know how... (I've tried to resolve complement by defining characteristic function like this: $\chi_{\bar A} = 1 - \chi_A$) Any ideas please? :-)
1
vote
1answer
356 views

Reduction to prove that the function is not computable

Use reduction to show that the following function is not computable, where P is any python program that takes a single input x: sotrue(P) = true, if P(x) returns true for every value of x, ...
1
vote
0answers
34 views

Is it really true that $K(x|y) = K(x,y) - K(y)$?

Denote by $y^*$ the shortest program computing the string $y$. In the main textbook and various papers of Li & Vitanyi, I have seen the following statements. The first is well established: the ...
2
votes
1answer
95 views

unary recursive language

I'm having trouble with this question: Given any language L is a subset of $\{0,1\}^*$, define the language $$\text{unary}(L) =\{0^{1x} | x \in L\}$$ The language $\text{unary}(L)$ is ...
2
votes
1answer
158 views

question about Gödel numbering

I have a question about Gödel numbering, it is trivial but I would like to know how can you know the length of an expression through its Gödel number. ¿? I think you can use a recursive function but ...
3
votes
1answer
145 views

Question about $\Sigma_n$-soundness

According to wikipedia (http://en.wikipedia.org/wiki/%CE%A9-consistent_theory#Definition): "$\Sigma_n$-soundness has the following computational interpretation: if the theory proves that a program C ...
1
vote
2answers
182 views

Question about computability of true/provable formulas

I would like to clarify some things related to the computability of the sets of all theorems and true formulas for the formal arithmetic. Consider the theory $T$ of formal arithmetic (the theory of ...
1
vote
2answers
209 views

I do not understand why the Turing computable sets of N are exactly the sets at level $\Delta_1^0$ of the arithmetical hierarchy

The reason I don't understand it is this. Take for example the twin primes conjecture, which is $\Pi_2^0$. The set of twin primes is computable right? (there is a Turing machine that enumerates all of ...
7
votes
2answers
363 views

Is there any generalization of the hyperarithmetical hierarchy using the analytical hierarchy to formulas belonging to third-order logic and above?

As I understand, hyperarithmetical sets are defined according to the analytical hierarchy, that is, second-order-logic formulas. There is a generalization of hyperarithmetic theory named α-recursion ...
4
votes
1answer
370 views

Is there a decidable theory in propositional logic whose consequences are not decidable?

I want to know if there is a decidable theory in propositional logic whose consequences are not decidable. If there is, can we have a constructive example or we can only prove the existence of it? ...
4
votes
1answer
85 views

Is every context free language equivalent to one whose grammar has only one non-terminal symbol?

A context free language is generated by a context free grammar, which can be expressed in the Backus-Naur form e.g. I believe that if we only allow one nonterminal symbol in the grammar, the resulting ...
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
526 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
48 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
602 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
612 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
614 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
49 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
117 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
142 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
179 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
420 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. ...
12
votes
2answers
195 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
455 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
106 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
116 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
216 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
306 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
202 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
244 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$ ...