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)

6
votes
1answer
107 views

A question on non-standard ordinals in $\alpha-$recursion

Let $M$ be an admissible set, namely, $M\models KP$ where KP stands for axioms of Kripke–Platek set theory. Denote $\beta=M\cap ORD$ where $ORD$ is the class of ordinals. I wanted to prove ...
3
votes
2answers
349 views

delta-zero formula and power of 2

How can we show that $x=2^k$ for some $k$ is equivalent (in the Naturals) to a $\Delta_0$ formula? So, I'm stuck at showing that 'y divides x' and '2 divides y' are equivalent in the Naturals to ...
0
votes
3answers
106 views

Binary expansion and correspondence of finite strings

How can we show that there is a one-to one correspondence between finite strings of the symbols 1 and 0 and the naturals $\mathbb{N}$. I was thinking along the lines of maybe using a 2-tuple, but ...
1
vote
1answer
65 views

Post Correspondence Problem

The alphabet consists of just two characters, $0$ and $1$. How do I go about proving that it's undecidable? I was thinking of reducing the general case to binary form meaning if the alphabet has ...
1
vote
3answers
76 views

a finite algorithm mapping from $\omega \times \omega$ to $\omega$ possible?

We know that $\omega \times \omega$ is isomorphic to $\omega$, but I am not sure if there would exist a finite algorithm mapping from $\omega \times \omega$ to $\omega$. An algorithm would of course ...
4
votes
1answer
146 views

The Permitting Method

Define the term late permitting in the following way: $C$ late permits an element $x$ to enter $A_{s+1}$ if for a fixed computable function $f$ with $f(n)>n$, there exists $y\leq x$ such that $y\in ...
1
vote
1answer
138 views

simple sets, cofinite sets, filters

Let $\mathcal S$ be the class of simple sets and $\mathcal C$ the class of cofinite sets. Prove that $\mathcal S\bigcup \mathcal C$ is a filter in $\mathcal E$. Definitions: An infinite set is ...
0
votes
1answer
79 views

Proving Decidable Language

Let $E$ be a Turing machine outputting a list of codes of Turing machines $\{\left \langle M_1 \right \rangle, \left \langle M_2 \right \rangle, ...\}$ where every $M_i$ is deciding some language ...
3
votes
1answer
47 views

Which diophantine polynomials generate these diophantine sets?

Via Matiyasevich's Theorem, it is easy to prove that the following sets are diophantine: $\{k\}$ $\{0, 1, \dots, k-1, k+1, k+2, \dots \}$ $\{0, 1, \dots, k\}$ $\{k+1, k+2, \dots\}$ Number 1 is ...
6
votes
1answer
518 views

What are $\Sigma _n^i$, $\Pi _n^i$ and $\Delta _n^i$?

Sometimes reading on wikipedia or in this site (and in very different context like topology, arithmetic and logic) I have found these symbols $\Sigma _n^i$, $\Pi _n^i$ and $\Delta _n^i$. They are ...
2
votes
1answer
576 views

Is this undecidable language recognizable?

Is this language: $L = \{\langle M\rangle : \text{$M$ is a Turing machine and $L(M)$ is decidable}\}$ which I know that is undecidable, turing-recognizable? Is its complement recognizable? ...
1
vote
2answers
740 views

Turing machine for balancing parentheses on a two letter alphabet

How to construct a Turing machine $M=(Q,\Gamma,b,\Sigma,\delta,q_0,F)$ which decides if a sting on the alphabet $\{(,)\}$ is ''balanced'' (e.g. $(()())$ is balanced and $))(($ or $()(($ is not) with ...
3
votes
1answer
204 views

Recursion schema and the arithmetical hierarchy

In computability we define the following basic functions, the zero function, the successor function, and the functions $I_{n,k}(x_1,\ldots,x_n)=x_k$ for $k\leq n$. Next we define three schemata for ...
4
votes
1answer
88 views

A paradox related to computable reals?

Let O be a computable ordering of all computable reals in ⟨0,1) (eg. first by length of programs computing them and then lexicographically). (it does not matter that they appear there more than one ...
6
votes
1answer
146 views

A topological example from Church's undecidability paper

A. Church, in his classical paper An unsolvable problem in elementary number theory in American Journal of Mathematics Vol. 58 No. 2. (1936), pp. 345-363, (available here), wrote: There is a class ...
3
votes
1answer
113 views

Is my logic here correct? Primitive recursion and diagonalization proof

I'm trying to understand diagonalization as it applies to proving that not all total functions are primitive recursive functions. For example, say that we enumerate all primitive recursive functions ...
2
votes
1answer
73 views

Proving a class of relations is closed under an operation

Given a class of functions $\mathcal{A}$ is closed under substitution and the operation $(\mu y)_{\leq z}$, where $$ (\mu y)_{\leq z}f(y, \vec x) = \begin{cases} \min\{y : y \leq z \land f(y, ...
3
votes
2answers
99 views

If $L\in REG$ then $M$ has a finite number of distinct rows

Let $L \subseteq \Sigma^{\star}$ and let $M^{\Sigma^{\star} \times \Sigma^{\star}}(\{0,1\})$ an infinite matrix such that for each $x,y\in \Sigma^\star$: $$ m_{x,y}=\begin{cases} 1 & x y\in L\\ 0 ...
0
votes
1answer
109 views

Computability function - how to express it in set theory/arithmetic hierarchy

Let's say that $f$ is computable function such that for particular inputs $x$ and $y$, $f(x) = 0$ and $f(y) = 0$. If we want to express this in logical form (arithmetic hierarchy formula), what would ...
0
votes
1answer
128 views

recursively enumerable of Godel numbering

There are statements for natural number x, like followings m: "x is even natural number" n: "x+1 is odd number and x>1" l: "x is positive integer multiple of two" m, n, l has same boolean value ...
2
votes
1answer
85 views

What's the error in this argument that Fin$\le_m$Inf

There must be an error in the following argument since Fin is not many-one reducible to Inf, I can't seem to find it. Here it is informally (I hope it's straightforward and not confusing): Take any ...
1
vote
1answer
83 views

For a one-to-one function is the pullback of a recursively enumerable set $f^{-1}[W_e] = W_{g(e)}$ where $g$ is one-to-one?

Let $\phi_e : \mathbb{N} \to \mathbb{N}$ be the recursive function coded by $e$ and $W_e = \{ x : \phi_e(x) \text{ is convergent}\}$. A set $A$ is recursively enumerable if $A = W_e$ for some $e$. ...
0
votes
1answer
127 views

completeness and creative

I'm trying to show that any complete $\Sigma_1^0$ set is creative. The definition of creative I understand is: if there is a total recurvise function f s.t. f(e) is an element of A iff f(e) is an ...
0
votes
1answer
71 views

recursive maps and decimal representation

I'm trying to think of an example of a real number $R$ such that the map $n \mapsto R[n]$, where $R[n]$ is the $n$th digit of the decimal representation of $R$, is not recursive. So I was thinking to ...
1
vote
1answer
157 views

recursive and creative theorem

How can we show that if A is creative, then A is not recursive. Only thing I can get out is the fact that if A is creative, if it is rec. enumerable and the complement(A) is productive. Thanks
1
vote
1answer
179 views

How does one prove that 1-generic set is not computable?

Without resorting to diagonalization proof of halting problem, how does one prove that 1-generic set is not computable?
2
votes
0answers
164 views

How to show Simp. and Creat. are $\Sigma^0_2$-Hard

Let Simp={$e:W_e$ is simple} and Creat={$e:W_e$ is creative} I'm having troubles showing these sets are $\Sigma^0_2$-Hard, ie that any $\Sigma^0_2$ set can be many-one reduced to them. I've already ...
0
votes
1answer
72 views

Identifying a pattern in an array

Is there a way to identifying a pattern and/or recursive function for an array? If yes, how can I do this. Could anyone please help me with some information and/or resource for this? Any help is ...
2
votes
1answer
195 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
310 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
123 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
111 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
81 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
54 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
65 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
178 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
194 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
100 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
127 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
110 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
107 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
95 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
199 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
240 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
258 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
306 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
195 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
216 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
161 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
62 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 ...