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.
1
vote
2answers
107 views
+200
Decidability and undecidability of a set or language
I want to find out whether the following sets are decidable or not. Generally speaking, what exactly should be done about it? Doing some research, I think a language or set is decidable if a Turing ...
1
vote
1answer
42 views
Recursive function with code $n$, whose output is the number $n$ itself
There is a recursive function with code $n$, whose output is the
number $n$ itself. That is $\phi_n$ is the constant function with value
$n$.
I've been toying with the idea of using s-m-n ...
1
vote
4answers
87 views
properties of recursively enumerable sets
$A \times B$ is an r.e.(recursively enumerable) set, I want to show that $A$ (or $B$) is r.e. ($A$ and $B$ are nonempty)
I need to find a formula. I've got an idea that I should use the symbolic ...
1
vote
0answers
19 views
Computational Complexity of the class of $\Delta_0$ functions (over $V_\omega$)
I would like to know where the class of functions whose graph is $\Delta_0$ (over $V_\omega$) fits in the computational complexity hierarchy. Also is there a nice notion of $\Delta_0$-reducibility ...
1
vote
2answers
80 views
Existence Universal goto-programm (turing machine)
May you can help me out with my problems with source codes. Well first of all we proved that for recursive functions $N:\mathbb N^2\rightarrow \mathbb N$ and $A^k: \mathbb N^k\rightarrow \mathbb N$ ...
2
votes
2answers
86 views
Is the difference of two recursively enumerable sets, reducible to $K$?
Is the difference of two recursively enumerable sets, reducible to $K$?
$W_x/W_y=\{z|z \in W_x \& z \notin W_y\}$
$K=\{x|\Phi_x(x) \downarrow\}$
$W_x= \text{dom}(\Phi_x)$
3
votes
1answer
56 views
Is this language decidable?
Is this language decidable?
$$\{x\mid \text{$x$ is the code of a Turing machine that always halts on $y$
in less than $y^3$ steps}\}$$
I think it is, because it halts in a finite number of ...
1
vote
2answers
58 views
decidability of $\{x|W_x \text{is different from K in only finitely many elements}\}$
Is the following language decidable? Please explain your argument as I want to learn how such problems must be solved to do the rest on my own.
$$\{x \mid W_x \text{ is different from K in only ...
1
vote
2answers
25 views
difference of 2 partial computable algorithms
I have 2 algorithms
Algorithm 1:
if( Condition1(input)==true )
print(input);
else
loop forever;
Algorithm 2:
...
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?
...
1
vote
2answers
79 views
non-recursive function
Give a direct proof that the set $\{x|\Phi_x(1) \downarrow\}$ (which is a set of program numbers that halt on input $1$) is not recursive.
I've got an idea that indirect proof must work. Assuming ...
1
vote
1answer
39 views
Rice’s theorem and recursion theorem
Prove Rice’s theorem using recursion theorem.
I need some hints as to what must be done about it. Please use Davis' book notation: Computability, Complexity, and Languages, Second Edition: ...
0
votes
0answers
56 views
Primitive Recursion — Definition by Cases
I would like to know if it is allowed to define bounded maximization by primitive recursion and definition by cases in the following way:
\begin{align*}
[\mathrm{max}\,R](x, 0) &= 0,\\
...
6
votes
3answers
83 views
What questions become answerable/computable given an uncountable character set?
Having reached the concluding portion of my first course in real analysis, one subject that I feel was not adequately addressed was the issue of cardinalities.
This is a subject I was interested in ...
3
votes
1answer
42 views
Determine whether two primitive recursive functions are equal
Is there an algorithm to determine whether two primitive recursive functions are equal (as mathematical functions)?
3
votes
1answer
57 views
Extending the recursive functions to higher classes in the aritmetical hierarchy
It is an important theorem that the recursive functions are exactly those which are definable by $\Delta^0_1$ formulas.
We have just finished the part about incompleteness in a course I'm TA'ing, and ...
2
votes
1answer
124 views
Injection from computable numbers into natural numbers
Each Turing machine which writes an infinite sequence of 1 and 0 can be regarded as
representing a (computable) real number (and of course each Turing machine represents a natural number by its ...
2
votes
2answers
56 views
Prove domain of partial computable function exists
Prove that there is an n such that $W_n$ = {$2n, . . . , 2n + n^2$}
Now I don't know where to start with this question, how can I go about answering it? Would I construct a computable function that ...
2
votes
1answer
74 views
Degree structure of $1$-Generic Set
We can construct a $1$-generic set $A\leq_{T}\emptyset'$, using an $\emptyset'$-oracle and finite extension construction as in the Kleene-Post theorem to meet all jump requirements. How can I show ...
1
vote
1answer
24 views
Numbering the Grzegorczyk Hierarchy.
I would like to know if there is a (known and maybe published) way to numbering, in a Gödel style, the functions belonging to every class in the Grzegorczyk Hierarchy and how could it be done.
2
votes
2answers
75 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?
1
vote
1answer
151 views
Second incompleteness and Model theorey
If we let $T$ be a consistent theory in the language of arithmetic $\mathcal{L}_A$ theory extending Peano Arithmetic — with specified numbering of formulas $\left[\cdot\right]$ and suppose that ...
4
votes
3answers
221 views
How many cpus needed to check a 100 million digit prime number efficiently?
If I had access to potentially large number of CPUs and wanted to quickly check 100 million digit numbers for primality using a map-reduce architecture, how many CPUs would be necessary? Each of the ...
0
votes
2answers
66 views
How is strong induction recursive?
I know that strong induction is equivalent to induction, and I know that functions that are defined by inductions are recursive.
So theoretically, strong induction should also give a recursive ...
0
votes
1answer
51 views
Infinite number of Proofs in Propositional Calculus?
Reading over a book on computability, it asserts that in P.C., if A is a theorem, then A has arbitrarily many proofs. I can't see how that would work, would you do an infinite loop in the sequence of ...
1
vote
0answers
44 views
Is discrete ultralogarithm harder than discrete logarithm?
Is computing $g^{xy} \bmod{s}$ from $g^{x} \bmod{s}$ and $g^{y} \bmod{s}$ easier harder or the same level of difficulty as computing
$g\uparrow\uparrow(xy) \bmod s$ from from $g\uparrow\uparrow x$ ...
6
votes
1answer
90 views
Primitive recursive function which isn't $\Delta_0$
What is the simplest/cutest example (and/or example with the most student-friendly proof that it is an example) of a primitive recursive function which isn't representable by a $\Delta_0$ wff?
0
votes
2answers
43 views
Can all programs be modeled as operations of elementary arithmetic operations on inputs?
In mathematics and computabiltiy theory, we treat
all inputs and intermediate results and final
outputs as natural number. While algorithms/programs themselves are considered natural
numbers, here we ...
0
votes
0answers
47 views
Can all programs reducible to ones with only arithmetic operations on inputs be simulated with polynomial overhead by arithmetic machine?
In Can all programs be modeled as operations of elementary arithmetic operations on inputs? and computabiltiy theory, I
asked:
we treat all inputs and intermediate results and
final outputs as ...
0
votes
0answers
156 views
binary string delta zero case
How to show that the binary string representing z is equal to the concatenation of the binary strings representing x and y (in that order), is a delta-zero condition?
For delta-zero, there must be ...
3
votes
2answers
171 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 ...
6
votes
0answers
54 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 ...
0
votes
3answers
80 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
2answers
137 views
Sequences of a computable function
Is there any computable function $f(n)$, which given any integer $n$ has been proven to return either $0$ or $1$ in finite time, and for which the statement "$f(1), f(2), f(3),\ldots$ contains ...
1
vote
1answer
39 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 ...
5
votes
1answer
136 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 ...
6
votes
3answers
329 views
Why are $\Delta_1$ sentences of arithmetic called recursive?
The arithmetic hierarchy defines the $\Pi_1$ formulae of arithmetic to be formulae that are provably equivalent to a formula in prenex normal form that only has universal quantifiers, and $\Sigma_1$ ...
1
vote
3answers
65 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 ...
2
votes
1answer
40 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
49 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 ...
6
votes
1answer
241 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
146 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?
...
4
votes
1answer
61 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 ...
1
vote
2answers
90 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 ...
1
vote
1answer
90 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 ...
3
votes
1answer
53 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 ...
5
votes
0answers
74 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
33 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 ...
0
votes
4answers
159 views
will computers replace (most) mathematicians? [closed]
We already have computers doing proofs and assisting mathematicians with generating proofs. I would expect that their presence will only grow larger with time as the algorithms become more practical.
...
2
votes
1answer
52 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, ...
