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
168 views

Proof of Kleene's T predicate being primitive recursive

As I am looking over Kleene's T predicate, I was unable to find why Kleene's T predicate is primitive recursive. Can anyone show why? (I know what primitive recursive is.)
0
votes
1answer
277 views

Recursively inseparable sets

I'm trying to show that there is a pair of $\Sigma_1^0$ recursively inseparable sets. From the definition, recursive inseparable is if there is no recursive set $C$ such that $A\subset C$ and $B\cap ...
0
votes
1answer
122 views

A real number being computable

In my text, it says that a real number $r \in \mathbb{R}$ is computable iff given $n$ one can compute $q \in \mathbb{Q}$ such that $\left|r-q\right| \leq 2^{-n}$. Can anyone show why it is the case? ...
2
votes
2answers
106 views

$\omega_1^{CK} - \omega$ - infinite or finite set? And boundary

I am curious whether $\omega_1^{CK} - \omega$ would result in a finite set or infinite set. Does anyone know what happens? Edit: OK, let me add one more question: Suppose that we take $\omega \cdot ...
4
votes
2answers
78 views

Proving induction from basic recursion lemma

Induction Principle: Let $A$ be a set such that $0 \in A$ and $n \in A \implies n + 1 \in A$. Then for all $n \in \mathbb{N}$, $n \in A$. Basic Recursion Lemma: For all sets $X, W$ and given ...
1
vote
1answer
53 views

analytical hierarchy and individual variable quantifiers

For analytical hierarchy, $\Sigma^1_0$ is usually defined as the class of formula that does not have any set quantifier - but does this mean that there can be any number of quantifiers for individual ...
0
votes
1answer
62 views

$\mid$ in simply typed lambda calculus

$e = x \mid \lambda x\!:\!\tau.e \mid e \, e \mid c$ So, what is $\mid$ in this example of simply typed lambda calculus? The syntax of the simply typed lambda calculus is essentially that ...
1
vote
2answers
175 views

Writing Fermat's last theorem in arithmetic hierarchy

Somehow connected with How natural numbers can be defined using primitive recursive $\Sigma_0^0$: OK, so here's how Fermat's last theorem is formulated: $$\forall x,y,z,n>2 \quad (x^n+y^n + z^n ...
1
vote
1answer
188 views

How natural numbers can be defined using primitive recursive $\Sigma_0^0$

$$S=\{x\mid (\exists y_1)\cdots (\exists y_r)P(x,y_1,\ldots,y_r)\}, \qquad P \text{ primitive recursive.}$$ I do get how some set of natural numbers (or numbers) can be defined with $\Sigma_1^0$ ...
4
votes
1answer
98 views

Why is computable function in $\Delta_{1}^0$?

I am not sure why computable functions are in $\Delta_{1}^0$. Can anyone explain this?
1
vote
2answers
118 views

The computability of Kleene's $T$-predicate

Why is Kleene's T-predicate computable? how to argue this using turing computability? would that be useful or writing it as some function
4
votes
1answer
107 views

$\Sigma^0_n$ complete sets

Does anyone know of a way of showing that a $\Sigma^0_n$-complete set is not $\Pi^0_n$ without having to appeal to $\Sigma^0_n$-universal sets? For instance a more direct diagonalization argument ...
2
votes
1answer
102 views

Computable function example

Suppose $p(x)\in\mathbb{Z}[x]$. How can we show that the function $b\to$ the least non-negative integer root of $p(x) - b$ is computable (if there is no such root, then the function is undefined)? ...
1
vote
1answer
94 views

Godel numbering and Turing jump

Given a set $X$ and a Gödel numbering $φ_i^X$ of the $X$-computable functions, the Turing jump $X'$ of $X$ is defined as $X'= \{x \mid \varphi_x^X(x) \ \mbox{is defined} \}.$ OK. But then ...
5
votes
2answers
186 views

How does second-order logic relate to lambda calculus?

How does second-order arithmetic/logic relate to lambda calculus? By lambda calculus, I mean both typed and untyped. And is there any relationship with recursive and recursively enumerable sets? ...
0
votes
1answer
238 views

NonRecursive Sets

I'm trying to show that the following are nonrecursive: $\{x \in \mathbb{N} \mid \phi_x(y) \uparrow\}$ $\{(x,y) \in \mathbb{N}^2 \mid \phi_x = \phi_y\}$ $\{(x,y) \in \mathbb{N}^2 \mid y \in ...
-3
votes
1answer
252 views

Computability of busy-beaver sequence? [closed]

We can draw a parallel between cellular automata and busy-beaver numbers. For example the initial case occupies some kxk square in the plane,leaving all the other cells emty, after how many ...
3
votes
0answers
289 views

How to derive Church-Kleene ordinal

Crossing-out: (How does one prove the existence of Church-Kleene ordinal? Also, why is it labeled as $\omega_1^{CK}$? And why is it first ordinal not hyperarithmetical, and is the first admissible ...
1
vote
1answer
180 views

Halting problem on 2 registers

How can we show that the halting problem on register machines equipped with only two registers is unsolvable. My intuition stems from assuming it is unsolvable on $n$ registers, but if we take a ...
1
vote
1answer
202 views

Recursively enumerable sets

How can we show that any diophantine set is recursively enumerable? To be r.e., we require that the characteristic function is recursive and thus we require set to be decidable. Only thing hat may ...
2
votes
1answer
158 views

Diophantine sets

I'm trying to show that the following sets are Diophantine: $\{(x,y)\mid x \leq y\}$ $\{(x,y)\mid x < y\}$ $\{(x,y)\mid x\text{ divides }y\}$ $\{(x,y,z)\mid x\equiv y \pmod z\}$ $\{(x,y,z)\mid x ...
1
vote
2answers
61 views

In complexity, Is the relationship between P and R known?

The relationship between P and NP is unknown; However, we can ask an "easier" question, what is the relationship between P and R (=decidable languages)? In other words, is there a (decidable) problem ...
2
votes
2answers
63 views

When is the complement of a diophantine set in the naturals also diophantine?

A diophantine polynomial is a (multivariable) polynomial with integer coefficients. If we write this polynomial as $p(x, y_1, \dots, y_n)$, then it defines the diophantine set $D_p = \{ x \in ...
2
votes
2answers
126 views

Complements of recursively enumerable subsets.

Let $A,B \subseteq \mathbb{N}$. If $A$ and $B$ are recursively enumerable, can we say anything about expressions like $A^c \cup B$, $A^c \cap B$, etc.?
0
votes
2answers
144 views

Church's Thesis

If we let $f$ be a computable function and define $h(x) = 1$, if $x$ is an element of $\operatorname{dom}(f)$ and undefined otherwise. I am trying to prove that h is computable via Church's Thesis. ...
2
votes
2answers
131 views

Is Turing-completeness decidable?

This may be a silly question, but is there an algorithm that decides whether any given model of computation is Turing complete?
4
votes
0answers
79 views

Is the measure induced by the Mandelbrot set computable on rational rectangles?

Is there a computable function that, given a positive rational number $\epsilon$ and a rectangle with rational corners $A$ returns a number $f(A,\epsilon)$ such that $|\mu(A \cap ...
3
votes
1answer
130 views

Are the brackets in formal box notation of recursive functions omittable?

So we know all recursive functions can be expressed as a finite sequence of symbols for the basic functions and processes composition, primitive recursion, and minimization. What I'm wondering is if ...
7
votes
2answers
196 views

Are there known natural problems of intermediate degrees of unsolvability?

I know there exist intermediate degrees of unsolvability, i.e. there are undecidable problems which can be reduced to the Halting Problem, but not vice versa. Are there any "natural" problems known or ...
1
vote
2answers
198 views

Recursive relation using successor function

What is the recursive relation for $$H(m)=2^{(m^2)}$$ using successor function recursive relation for multiplication: $$mult(x,0)=0; mult(x,S(y))=add(x,mult(x,y))$$ recursive relation for addition: ...
1
vote
1answer
91 views

Recursive functions, successor function

How to show that the power function $\displaystyle A=2^{m^2}$ is primitive recursive based on successor function? Thanks much in advance!!!
3
votes
1answer
183 views

Explain why if the language A is recursive, then A is reducible to 0*1*

I'm in a theory of computation class and there is a problem that I think I am way overthinking. Can anyone point me in the right direction with the following: Give a short justification of the fact ...
1
vote
1answer
348 views

Converse of Collatz Conjecture

How to write a pseudocode program that halts only if the Collatz Conjecture is false. Thanks much in advance!!!
1
vote
1answer
173 views

Recursive relation and predicate

If we let P(x,y) be a primitive recursive relation and g(x) be a primitive recursive function. Then how to show that there exists a y < g(x)*P(x,y) is a primitive recursive relation? And how can ...
2
votes
2answers
478 views

Turing machine that computes if two integers are equal

I am a philosophy student taking a Logic II class and I am scared. I have encountered the following question and I am bewildered about where to start or what to do. Design a Turing machine to ...
0
votes
1answer
117 views

Primitive Recursion maps

Is there an example of a bijective map pi: N^2 --> N (where N = natural #'s) which is primitive recursive? I'm thinking along the lines of projection function but can't quite spell it. Are there some ...
3
votes
1answer
91 views

$\omega-$model for $RCA_0$ and Proof of Ramsey's Theorem in $ACA_0$

These are two questions I encounter in Reverse Mathematics recently. In the characterization of the $\omega-model$ $M$ for $RCA_0$, the necessary and sufficient condition is $M$ is non-empty and ...
1
vote
1answer
111 views

Difference between language is decidable and function calculable by turing machine

I'm trying to understand the difference between saying a language is decidable and a function is calculable by a turing machine. I must have understood something wrong, because for me it doesn't make ...
3
votes
1answer
100 views

Sources on a category of ordinals

all I'm reading old papers on generalized recursion theory, and I've run across a paper by Van de Wiele ("Recursive dilators and generalized recursions") that 'lives in' the category ON, whose ...
1
vote
1answer
216 views

Ackermann function in terms of higher order recursion

Wikipedia provides a higher-order definition of Ackermann function. First it gives the normal recursive definition \begin{equation*} A(m,n)=\left\{ \begin{array}{ll} n+1 & \text{if $m=0$} \\ ...
1
vote
1answer
229 views

Representing Recursion and Primitive Recursion diagrammatically

I'm interested in how Recursion, and Primitive Recursion, could be represented diagrammatically. It occurred to me that this would be a good way of seeing the difference. Also, I'm interested in how ...
2
votes
1answer
76 views

Prove $B = \{ \varphi_n(n) | n \in \mathsf{K} \}$ to be recursive

The set $B$ is the range of universal function given the domain $\mathsf{K}$, where $\mathsf{K} = \{ n | \varphi_n(n) \textit{ halts} \}$. How can we prove such claim?
3
votes
1answer
163 views

Members of (lightface) Borel sets

I'm fairly certain this question has a very simple answer, and that I've learned it before; I just can't seem to remember it. Suppose I have a nonempty lightface Borel set $X\subseteq 2^\omega$. What ...
0
votes
1answer
66 views

On Cardinalities of $\mathcal{RE}$ and $\mathcal{P}(\mathbb{N})$

We denote $\mathcal{RE}$ as the universe set of recursively enumerable sets. A set is recursively enumerable iff its semi-charactersitic function is computable (one can write its semi-verifier). The ...
3
votes
3answers
188 views

Definition of computability of real numbers?

What exactly does it mean to say that a real number $x$ is computable? I can think of two reasonable definitions but I am not sure whether or not they are equivalent: 1) There is an algorithm which ...
109
votes
1answer
3k views

What properties of busy beaver numbers are computable?

The busy beaver function $\text{BB}(n)$ describes the maximum number of steps that an $n$-state Turing machine can execute before it halts (assuming it halts at all). It is not a computable function ...
2
votes
1answer
79 views

Proof that an inverse of a possibly noncomputable function is possibly not decidable

I'm stuck with the following homework: Given an fixed function $f:\mathbb{N}\to\mathbb{N}$. $f$ is an arbitrary (possibly not computable, possibly partial) function. Show that the set $\{f(42)\}$ is ...
2
votes
2answers
800 views

Examples of Many-one reductions.

I'm trying to wrap my head around many-one reductions for an assignment in Mathematical Logic. The assignment is to show $A$ r.e $\Leftrightarrow$ $A\leq_m K$ where $K=\{x\in\mathbb{N}\ |\ x\in ...
1
vote
1answer
118 views

Space : Kolmogorov complexity :: time and space : ___?

It's well-known that the Kolmogorov complexity is uncomputable, essentially because of the halting problem: you can list all programs of length less than one known to generate a given string, but you ...
7
votes
2answers
501 views

What is the relationship between ZFC and Turing machine?

I did not learn Logic properly but so far I understand that proof systems can be viewed as a kind of machine. For proof system, ZFC seems to be the most powerful one that we use so far. Similarly, for ...