Questions about which problems are computable, or in general any question in recursion theory. Questions about the difficulty of solving particular problems should be tagged complexity.
0
votes
1answer
54 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
66 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 ...
2
votes
1answer
42 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
113 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
49 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
135 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
78 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
125 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
35 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
51 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
74 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
97 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
64 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 ...
5
votes
2answers
44 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
40 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
0answers
31 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
94 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
74 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
79 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
77 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
77 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 ...
1
vote
1answer
57 views
Computable function example
Suppose p(x) an element of Z[x]. How can we show that the function
b --> the least non-negative integer root of p(x) - b
is computable (if there is no such root, then the function is undefi ned)?
One ...
1
vote
1answer
56 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 ...
3
votes
2answers
87 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
156 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 ...
-2
votes
1answer
103 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 ...
2
votes
0answers
100 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
118 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
105 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
114 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
38 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
1answer
34 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
101 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
135 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
76 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?
2
votes
0answers
41 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 ...
2
votes
1answer
55 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 ...
6
votes
2answers
80 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
78 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
48 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
57 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
203 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
142 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
122 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
70 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 ...
1
vote
0answers
28 views
Kolmogorov complexity and type of string
My question about well-known theorems:
Theorem: Kolmogorov complexity is not a computable function.
And, related, Chaitin's incompleteness theorem.
...
3
votes
1answer
52 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
49 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 ...
0
votes
1answer
50 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
82 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$} \\
...
