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)

3
votes
1answer
84 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
78 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 ...
1
vote
0answers
57 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
111 views

Many-one Reducibility Understanding Problem [closed]

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
vote
1answer
74 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
104 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
88 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 ...
-1
votes
1answer
58 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
0
votes
1answer
53 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
100 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?
0
votes
3answers
36 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
23 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
37 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
79 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
38 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
73 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?
0
votes
1answer
85 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
49 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
36 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
70 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
73 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
57 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
30 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
83 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
52 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
27 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
68 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
137 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
104 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
101 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
31 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
75 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
30 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
35 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 ...