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.
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 ...
1
vote
2answers
83 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 ...
15
votes
1answer
290 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
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 ...
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 ...
0
votes
1answer
63 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
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 ...
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 ...
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 ...
4
votes
0answers
130 views
algorithm for solving diagonal quadratic equations over real or complex numbers
I found the following statement in the paper http://www.math.uni-bonn.de/~saxena/papers/cubic-forms.pdf (page 22, in the middle):
For $\mathbb F\in\{\mathbb R, \mathbb C\}$ and $b, a_i\in\mathbb ...
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 ...
2
votes
0answers
99 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 ...
2
votes
0answers
39 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
0answers
164 views
Deciding whether a formula is provable with a fixed number of universal generalizations
Let $y$ be Godel number of some formula which is derivable in some first-order logic. $F(y,n)$ is true if and only if the number of usage $Gen$(universal generalization) inference rule in any ...
2
votes
0answers
86 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 ...
2
votes
0answers
92 views
constructive ordinal and $\Delta^1_1$ predicate
Everything I know on this subject comes from Sacks book : "Higher recursion theory"
Let $\mathcal{O^Y}$ be the set of codes for ordinals constructive in $Y$.
We should have the result that $A ...
2
votes
0answers
144 views
Further question on “uncountable” Turing Machine
Having read An "uncountable" Turing Machine? I have further questions that I don't believe it addressed. (I'm a programmer, not a mathematician so I apologize if this is stupid or the ...
1
vote
0answers
45 views
Halting problem some properties
I am referring a little bit to my previous question on http://math.stackexchange.com/questions/392843/existence-universal-goto-programm-turing-machine#=
Let $f(n)$ be the output of the universal ...
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
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$ ...
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.
...
1
vote
0answers
30 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 ...
1
vote
0answers
119 views
Recurrence relation for the digits of the integer square root in binary
I was investigating a question on the Electrical Engineering Stack Exchange site, available here: ...
1
vote
0answers
69 views
What would an “algebraic axiomatization of the partial recursive functions” be?
Hartley Rogers in his "Theory of recursive functions and effective computability" (page 55 in the first edition) writes
"What resemblance types are also isomorphism types? A final answer to this ...
1
vote
0answers
40 views
Computability of “isomorphism existence” between special cubic number fields
Let $a$ be a rational number such that the polynomial $P_a=X^3-X-a$ is irreducible, let
$\alpha_{a}$ denote a root of $P_a$ and let ${\mathbb K}_a={\mathbb Q}(\alpha_{a})$. Similarly, let $b$ be a ...
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,\\
...
0
votes
0answers
49 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 ...
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 ...
0
votes
0answers
52 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 ...
0
votes
0answers
53 views
0
votes
0answers
83 views
Master Theorem $T(n)=4T(n/8)+n^(3/8)$
My try was :
$$f(n)= n^3/5=n^{0.6} g(n) = n^{\log_8}(4) =n^{0.667}$$ so $f(n)<g(n)$
So $f(n) = \Omega(n^{\log_8}(n) + \epsilon)$ but with regularity condition
$4f(n/8) \le cn^{3/5}$ ,for $c$ ...
0
votes
0answers
38 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
0answers
46 views
Double Recursion Theory
What is a doubly recursive or non-primitive recursive function?
What are some well known doubly recursive formulations?
Can someone explain with some illustrations?
0
votes
0answers
79 views
Relationship between $\Sigma_{1}$ and $\Pi_{1}$ functions (Logic)
I am working on the following homework problem for a logic class on Godel's incompleteness theorems and the following question is asked.
Is the converse of Theorem $13.1$ true? Explain.
Theorem ...
0
votes
0answers
47 views
Is there a standard maximality operator?
Is there a standard symbol for the maximization operator, much like μ for minimization?
