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
0answers
22 views

Computable models of ($\omega$, <) without computable isomorphism

I read somewhere that "it is easy" to construct a computable presentation for the model ($\omega$, <) so that any computable isomorphism between this construction and the usual presentation of ...
1
vote
1answer
31 views

What techniques are there to search for first order sentence equivalence?

Suppose we have a first order sentences $\phi$, $\psi$, and $\chi$ such that: $\phi$ $\longleftrightarrow$ ($\psi$ $\land$ $\chi$) And $\phi$ and $\chi$ are known or fixed. How can we search for a ...
1
vote
2answers
36 views

Proof that INF (the set of indices of Turing Machines that halt on infinitely many inputs) is not computably enumerable, I.e. $\not \in \Sigma_1^0$

I got curious about this today when looking for sets to proove aren't $\Sigma_1$ as exam prep. Unlike with its complement, FIN, a run of the mill contradiction was not easy to come by (perhaps I'm ...
3
votes
1answer
68 views

Proof that $\{ e \ | \ \forall p$ prime$: \varphi_e (p) \downarrow \}$ is not $\Delta_2$

This is a problem I've come across in my exam studies, and neither me nor my friend in the same course have been able to solve, so it would be good to see how it's done before the exam in a couple of ...
1
vote
0answers
48 views

“Building blocks” for computable functions

In an (otherwise very enlightening) answer to another question of mine the question came up What functions are allowed as building blocks for computable functions? I was astonished that there ...
2
votes
0answers
30 views

Generating interesting random TMs

To get a more intuitive understanding of the halting problem I want to generate some random TMs and see how they behave, what some heuristics can tell about them, etc. The problem is that, if I ...
2
votes
1answer
78 views

Functions with and without distinction of cases

Consider computable functions $f: \mathbb{N} \rightarrow \mathbb{N}$, given as formulas. I assume that it is clear for at least some of them whether they contain a distinction of cases: $$f(n) = n$$ ...
1
vote
0answers
37 views

Meaning of Biinterpretability.

I'm reading this paper: http://www.math.cornell.edu/~shore/papers/pdf/hyp9.pdf and I am struggling with the meaning of Biintereptability, to quote the paper A degree structure $D$ is ...
-1
votes
1answer
58 views

Function Combination on Computer Science

I read some material on Computational Function, every one could describe the result of following combination? suppose $g_1(x)=3x$, $g_2(x)=4x$, $f(x,y)=x+y$, how we compute combination of $f$ with ...
0
votes
0answers
72 views

Primitive Recursive Predicate Challenge

I'm an Computer scientist, and I recently ran into a challenge. If we have primitive recursive predicate $P(x), Q(x)$, I think that all of following 4 expressions can be primitive recursive. Any hint ...
0
votes
0answers
48 views

Recursive Set and Complement Problem

if we have $$A=\{x:|W_x\ne\phi\}$$ can we say always my tight listed below is true? $A$ is recursive , $A$ is r.e, complement of $A$ is r.e, complement of $A$ is not recursive?
1
vote
1answer
82 views

Recursive Set Challenge

we knoe also we know for example if A be any arbitrary r.e set. can we always Necessarily the following is TRUE ? (always) any description is good. (bar sign means complement)
0
votes
0answers
48 views

Proof: All recursive functions are arithmetic (logic)

So I'm trying to understand the proof of the following statement: > All recursive functions are arithmetic The proof begins with: "It is sufficient to show that all arithmetic functions satisfy ...
2
votes
1answer
34 views

Hausdorff dimension of computable real numbers

This might be a trivial question but do the computable numbers have a positive Hausdorff dimension?
1
vote
0answers
66 views

Is the Mandelbrot set computable?

This is a weakened version of Is the measure induced by the Mandelbrot set computable on rational rectangles? ; Given a (computable, or rational) rectangle in the complex plane, is it computable ...
1
vote
0answers
69 views

Efficient algorithm for calculating the tetration of two numbers mod n?

I'm trying to study the algebraic properties of the magma created by defining the binary operation $x*y$ to be: $ x*y = (x \uparrow y) \bmod n $ where $ \uparrow $ is the symbol for tetration. ...
-1
votes
2answers
54 views

How-to determine whether a given set is recursively enumerable?

I'm stuck with this problem I have to solve. Set $A = \{ x | \Phi_{x}(x): defined \}$ Set $B$ is produced from set $A$ by taking out all even numbers. Is set $B$ r.e.? How does one prove that?
0
votes
1answer
95 views

Uncomputability of $a<b$ or $b<a$

Is it possible to prove the existence of two real numbers $a, b$ that have the property that it is uncomputable whether or not $a<b$?
2
votes
0answers
29 views

Bijection of simple set

Let $X$ is simple set (http://en.wikipedia.org/wiki/Simple_set) $Z \subset X$ is infinite recursive set. $Y = X$ \ $Z$. How to prove that there is a computable bijection $f$ that $x \in X ...
5
votes
1answer
53 views

Nonstandard models of PA with a decidable order relation.

There this exercise in Models of Peano Arithmetic (Kaye 1991, p.157), which asks to define a recursive binary relation on $\mathbb{N}^2$, such that $M \upharpoonright < $ is isomorphic to ...
5
votes
1answer
80 views

Proving that $\Omega = (\lambda x.xx)(\lambda x.xx)$ is not typable in the simply typed lambda calculus

I am trying to prove that $\Omega = (\lambda x.xx)(\lambda x.xx)$ is not typable in the simply typed lambda calculus. Surprisingly, different textbooks and lecture notes do not contain that proof, ...
0
votes
0answers
35 views

Is there a fast algorithm for computing the $(2^n)+1$ th last digit of $3^{2^n}$ in base $2$?

Is there an algorithm such that for some polynomial p, it always computes the $(2^n)+1$ th last digit of $3^{2^n}$ in base $2$ in at most p(n) steps for all nonnegative integers n? I'm only asking if ...
2
votes
1answer
66 views

Question about the definition of Diophantine sets

I am currently reading "A Course in Mathematical Logic for Mathematicians" by Manin. The book defines Diophantine sets as follows: The projections of the level sets of a special kind of primitive ...
2
votes
1answer
160 views

Why should we accept the existence of subsets $A$ such that neither $A$ nor $A^c$ are recursively ennumerable? And how can we persuade others?

Encode every pair $(t,x)$ (where $t$ is a Turing machine and $x$ is an input string) as a distinct natural number. Then the halting subset $H$ fails to be recursive. $$H := \{(t,x) \in \mathbb{N} ...
2
votes
1answer
50 views

Prove that these Sets Containing Infinitely Many Incompressible Strings Exist

We define a set $A$ to be special if: $$\liminf_{n \to \infty} \frac{|A^{\leq n}|}{n} = 0$$ I want to prove that there are special recursive sets that contain infinitely many incompressible strings. ...
1
vote
0answers
26 views

Directed Hamiltonian Reduction

The reduction function given by Richard Karp in 'Reducibility among combinatorial problems' for Directed Hamiltonian Cycle $\leq_{p}$ Undirected Hamiltonian Cycle goes as follows : for input $G = ...
3
votes
1answer
67 views

A constructive algorithm for a jump of a low set.

Suppose we have an oracle Turing machine which, with $K$ (the halting problem) as an oracle, computes a low set $A$. ($A$ is low if $A'\equiv_T K$) Is there an algorithmic way of obtaining a Turing ...
4
votes
3answers
134 views

Diophantine equations and Hilbert's 10th Problem, how did MRDP do it?

I'm having a bit of trouble understanding the Wiki explanation of MRDP's (Matiyasevich, Robinson, Davis, Putnam)'s Theorem, which explains that Hilbert's 10th problem is unsolvable. The MRDP ...
1
vote
1answer
28 views

Polynomial Reduction for restriction

I ran across a polynomial reduction that used the fact that one language was a restriction of the other. Is that statement really true? $$ L_1 \subseteq L_2 \rightarrow L_2 \leq_{p} L_1 $$ Thanks!
1
vote
1answer
103 views

Computability: why any m-degree a is denumerable?

The problem printed in Cutland 9-2.9-6 is wrong, it should be countable, not denumerable m-degree is an equivalence class of the relation $\equiv_m$(many-one equivalent). Question: Why any ...
0
votes
2answers
37 views

Proving something is primitive recursive

I'm trying to prove $f(n) = 2n$ is primitive recursive. I understand that for something to be primitive recursive it must have the following properties: $0(x)=x$ the zero function $s(x)= x+1$ the ...
1
vote
0answers
100 views

Range/Image of a Non-Decreasing Total Recursive Function is Recursive

How do I show that the range of a non-decreasing, total-recursive function is recursive? I've made reference to this question, but the method used there is not clear to me. My attempt: Let $f$ be ...
2
votes
1answer
29 views

Problem from Cutland's Computability

Is it true that if $$ A \equiv_m \bar{A} $$ then A is recursive? I think it is true but I can't prove it. Appreciate your help!
3
votes
1answer
40 views

Are computable functions closed under “less than”?

Suppose f and g are functions from N to N, f is computable, and f>=g. Is g also computable?
2
votes
1answer
74 views

Turing degrees of models of ZFC and naming big numbers

Before asking my question, let me give some motivation which could help getting better answers. In this MO question, Scott Aaronson was trying to use the concept of "definable number" to create ...
0
votes
1answer
29 views

Efficiency LL and LR parsing

My question is, is an LL parser or an LR parser more efficient (in big-O terms) ? I don't mean in terms of coding the parser, but rather in the context of the runtime of the parser. Is there a ...
0
votes
2answers
31 views

How can I identify that an instance of Boolean SAT problem remains hard or not?

While I was studying SAT problem and its different instances, in Algorithms for the Satisfiability (SAT) Problem: A Survey by J. Gu et. al PDF, I came up with this instance, not mentioned there, but I ...
0
votes
1answer
34 views

Diagonalization out of partial recursive functions

So generally partial recursive functions don't diagonalize. But isn't this function an exception? $\phi(x)=\lambda_{x}(x)+1 $ if $\lambda_{x}(x)$ halts and $0$ else. Completely no clue... It seems ...
1
vote
0answers
23 views

Show $f(x)$ is partial recursive using the

So I want to show that the function $f(x)=0 $ if $x$ is even and not defined otherwise, is partial recursive using the $\mu$ operator (bounded search function, which is partial recursive). Plan is to ...
0
votes
1answer
51 views

Constructive fixed-point theorems where finite iteration yields the fixed point

I would like to show that $p$, a fixed point of some effective map $f : S\rightarrow S$, can be constructed effectively. Ideally, I would like there to exist a finite $n$ such that $p = f^n(p_0)$, ...
1
vote
0answers
63 views

Showing the class of all recursive sets is recursively enumerable.

Correct? Proof: Let D = {$A_i$ |$A_i$ is a recursive set$\}$. Take $z \in D$. Thus $z = A_i$ for some $i\in N$. Then: $\exists{f}$ such that for any choice of $A_i$ $\in$ D: $f(x) = 1$ if $x ...
3
votes
2answers
91 views

How does undecidability of 'theoremhood' imply that human ingenuity is necessary in mathematics?

In Robert Stoll's "Set Theory and Logic", there is the following passage on effectiveness of theorems (p. 375) : Mathematical logicians have shown that for many interesting axiomatic theories ...
2
votes
0answers
30 views

Clarification of the argument for the set of total recursive functions not being recursively enumerable?

I read that the set of partial recursive functions is recursively enumerable while the set of total recursive functions is not. Isn't the set of total recursive functions a proper subset of the set of ...
2
votes
2answers
152 views

How can the Gödel sentence be Pi_1

The Gödel sentence must be provable or unprovable by itself - you have to resolve all definitions until it only uses the elementary symbols of Peano arithmetic. What is the correct way to resolve ...
1
vote
1answer
42 views

Are all polynomial-bounded functions computable? [closed]

Let $f = O(g)$, where $g$ is a polynomial. Then is $f$ computable? Let $K(s)$ be Kolmogorov complexity of a string $s$. It's an incomputable function. No. Let $f(x) : \Bbb{Q} \to \Bbb{R}, \ f(x) = ...
0
votes
3answers
79 views

Having trouble understanding Cantors proof that real numbers are uncountable

I found this video very easy to follow and understood the proof. https://www.youtube.com/watch?v=mEEM_dLWY0g However, I am still having trouble understanding the proof presented to me in my csmath ...
0
votes
0answers
26 views

Not every polynomial in $\Bbb{Z}_p[x]$ can be factored, but can you do next best?

If $f \in R = \Bbb{Z}_p[x]$ is irreducible or doesn't have many factors then it could be hard to compute? Possibly, I'm not saying, but... any way, what if $f = h - g$ where $h, g$ are heavily ...
0
votes
1answer
27 views

Any problem computable in $k$ memory slots can be computed with polynomials.

Let our memory slots be represented by elements of $\Bbb{Z}_p$ for a prime $p$. $k$ memory slots would be $k$ copies of the ring: $R = (\Bbb{Z}_p)^k$. Suppose that for a problem $f : X \to Y$, ...
1
vote
2answers
103 views

Let A, B be infinite recursive sets with infinite complements. Show that A≡B.

My question is from Hartley Rogers' textbook (1967). Here's how I'm thinking about this so far. I know given infinite recursive sets A, B with infinite complements by theorem II of the current ...
2
votes
1answer
111 views

$\textbf{Q}$ fails to prove some correct $\forall$-rudimentary sentence

Show that the existence of a semirecursive set that is not recursive implies that any consistent, axiomatizable extension of Q fails to prove some correct $\forall$-rudimentary sentence. I ...