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)

-1
votes
1answer
29 views

Set of Logical Result Problem [on hold]

If we have a set of predicate formulas $A$, and there is an algorithm such that for every predicate formula $X$, (with input $X$), output YES iff $X \in A$. My question is about set of logical result ...
1
vote
0answers
32 views

Is a set $\{ e \in \mathbb{N} | \#\{x \in \mathbb{N} | \phi_e(x) \downarrow \} = \#\mathbb{N}\}$ computable?

Denote every partial computable function $f$ with its Godel number $e \in \mathbb{N}$ by $\phi_e$. Then let the halting set of $\phi_e$ be $W_e=\{x \in \mathbb{N} | \phi_e(x) \downarrow \}$ where ...
1
vote
2answers
52 views

How many recursively definable groups are there on $\mathbb{N}$?

How many non-isomorphic, (non-free), non-trivial, recursively definable groups are there on $\mathbb{N}$? I know we can at least get 1. Let $F:\mathbb{N} \to \mathbb{Z}$ be the "natural bijection". By ...
2
votes
1answer
31 views

Primitive-recursive functions and polynomial equations

I am looking for examples of primitive-recursive functions $f:\mathbb{N}\rightarrow\mathbb{N}$ that can not be written as a pair of polynomials, i.e. $$f(n) = m \Leftrightarrow P(n,m) = Q(n,m)$$ ...
4
votes
2answers
71 views

Uncomputability of subset relation

I suppose this obvious question should already be answered in plenty of places, but for some reasons I cannot find a proof of this anywhere. Prove or disprove that their exist a set $X$ that is ...
-2
votes
0answers
31 views

Maximum number of compressed RLE strings under any given length

Given a random string of length L (for instance, "01100010000101" of length "14"), and knowing that this string is only numerical, how many other strings under the form Y one can achieve by ...
2
votes
1answer
54 views

Bijection between computable reals and rationals?

This wikipedia article http://en.m.wikipedia.org/wiki/Computable_number#Properties suggests that there is such a bijection. How does it look like? And how to map computable transcedentals like pi to ...
1
vote
1answer
53 views

Is there a more general proof for the halting problem?

Note:If this question is better suited for a different site, please tell me in the comments. Summary:Is there a proof for the impossibility of the halting problem that doesn't involve calling it on ...
-4
votes
1answer
148 views

Primitive Recursive Predicate Problem [closed]

i get trouble with 2011 midterm exam question. if P(x) and Q(x) be a primitive recursive predicate. which of the following is not a primitive recursive? anyone could describe it for me? 1) $P(x) ...
0
votes
1answer
67 views

$\{x: 2x ∈ M\}$ is R.E Set [closed]

In computability theory, traditionally called recursion theory, a set $S$ of natural numbers is called recursively enumerable, computably enumerable, semidecidable, provable or Turing-recognizable if: ...
1
vote
0answers
47 views

Is this proof for the undecidability of $\beta$-normalisation in $\lambda$-calculus valid?

The proofs I have so far seen for the undecidability of $\beta$-normalisation all make use of Gödel numbering in order to first prove the more general Scott-Curry theorem. As an exercise, I have tried ...
-1
votes
1answer
100 views

Many-one Reducibility Understanding Problem

We know for every set $B$, that be r.e have: $$B\leq_mK$$ (The set $B$ is many-one reducible, or m-reducible, to the set $K$) we know $K$ is r.e and define: $$K=\{ e:e\in W_e\}$$ my challenge is: ...
-1
votes
1answer
73 views

Computation & R.E Set Problem [closed]

i ran into a old-midterm question recently, without any definition and tutorial Suppose A is a subset of Natural Numbers that includes all numbers except some finite numbers. why A ...
1
vote
1answer
71 views

Big Questions in First Order Logic

if $\Sigma$ is a r.e set (half decidable) of sentence in first order logic, the set of logical result of $\Sigma$ is Recursively Axiomatizable. why this is false? or maybe it's true? ...
2
votes
1answer
82 views

Is it decidable: is there an input for which turing machine will move its head left?

$L=\{\langle M \rangle | M $is a Turing machine and $\exists$ input $x$ such that in $M(x)$ running $M$ moves its head left at least once $\}$ Is $L$ decidable?
3
votes
2answers
85 views

Distinguishing sets according to more fine-grained notions than cardinality.

I'm interested in distinguishing sets according to more fine-grained notions than cardinality. Now I don't know a thing about computability theory, but it seems to me that considering sets up to ...
0
votes
1answer
50 views

Computable Set & Function

we know that i read this sentence are true? can anyone say an example for following sentence? there are a non computable set A such that
1
vote
1answer
44 views

Logic & Computability Problem

i read this sentence in one exam that be false. anyone could say why? if predicate H(x) become false when a program with code r(x) halt on input l(x), then H be a computable predicate.
-1
votes
1answer
67 views

Turing & Computability & Computation

We know if we have: we can show (T=t= Turin Redu.) but i have no idea why this relation be correct? any idea?
2
votes
0answers
50 views

Big Challenge in TM & R.E Set [closed]

we know that Halting problem {(M.w) | M halts on input w} is r.e but not recursive. i see the following sentence in one book. "the set of {(M.w) | M halts on input w and M is a TM}} is not r.e" ...
0
votes
3answers
24 views

Recursive Set in Partial Computable Function Problem

Suppose $A, B, C$ are disjoint set such as shown on this figure. $f_1(x), f_2(x), f_3(x)$ is partially computable function. why $A,B,C$ is recursive set?
2
votes
0answers
20 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
29 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
26 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
63 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
45 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
27 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
72 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
31 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 ...
0
votes
1answer
55 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
70 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
42 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?
0
votes
1answer
63 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
1answer
47 views

Complexity & Computation & Logic Problem [closed]

As i study for prepare to CS Final exam, i have some challenges. can i say all of following statements are true? 1) each infinite recursive set, is union of two disjoint infinite recursive set? 2) ...
0
votes
0answers
44 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
30 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
46 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
37 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. ...
0
votes
2answers
50 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
92 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
27 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
52 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
51 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
34 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
63 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
157 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
47 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
25 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
65 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
107 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 ...