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
1answer
40 views

Infinite sets having no RE subsets

I'm back trying to learn recursion theory on my own. I'd like to prove the following result: There exists an infinite set having no infinite R.E. subset. Constructive comments are appreciated. Proof: ...
2
votes
3answers
87 views

A mathematically mature introduction to Turing Machines and Computability [reference-request]

In the computer science course for mathematicians held at my university Turing Machines have been presented very briefly. So much so that I didn't quite get why they are relevant to mathematics. I did ...
1
vote
2answers
40 views

let A be a $2\times 2$ matrix . Then the smallest number $n\in \mathbb N$ such that $A^n=I$ is

let A be a $2\times 2$ matrix $\begin{pmatrix} \sin \frac \pi {18} & -\sin \frac {4\pi} {9}\\ \sin \frac {4\pi} {9}&\sin \frac \pi {18}\end{pmatrix}$. Then the smallest number $n\in \mathbb N$ ...
4
votes
0answers
23 views

Is the limit of a recursive sequence of recursive ordinals itself a recursive ordinal?

Is the limit of a recursive sequence of recursive ordinals itself a recursive ordinal? If so, is there a nice proof of this?
1
vote
1answer
30 views

Can differential calculus (limits, integrals, derivatives) be encoded in lambda calculus?

I am wondering, if the Church-Turing thesis holds (all effectively calculable functions are computable by Turing machines/lambda calculus) and I can compute the limit of a function by hand, what is ...
0
votes
1answer
29 views

Help understanding a 'reversing a string' Turing Machine

I am having a bit of a confusion understanding some transitions in a Turing Machine. Its an example from Introduction to Languages and the Theory of Computation by John C. Martin. I've attached the ...
1
vote
0answers
32 views

Turing Machine That Accepts Machines With Undecidable Languages

So I'm reviewing my Computability notes for my final, and I understand how reduction arguments work, but I'm having trouble framing one for the following Turing machine: Undecidable TM = { ⟨M⟩ | L(M) ...
-1
votes
1answer
25 views

proof with mapping reduction to Htm ,that p is undecideable [closed]

I am trying to prove with mapping reduction to Htm that P is undecidable and P={[m]|m is a Tm that accepts inputs of form ww}. I tried to build f([m,w]) = [m'], but failed to do so. Any ideas?
6
votes
1answer
123 views

Turing invariance on large sets

Definition: A function $f: 2^{\omega} \rightarrow 2^{\omega}$ is Turing invariant if $x \equiv_T y \rightarrow f(x)\equiv_T f(y)$. Question I (under $ZFC$): Let $f: 2^{\omega} \rightarrow 2^{\omega}$ ...
1
vote
2answers
51 views

Are there undecidable problems for which a solution has been found?

I mean are there examples of problems that have been proven to be undecidable, in the sense that it would not be possible to devise a deterministic computer program that outputs a solution for an ...
0
votes
0answers
74 views

could a machine $\mathfrak{D^+}$ be made to produce $\beta$ so the diagonal argument could be used on computable numbers?

I was reading Turing's paper "On computable numbers, with an application to the Entscheidungsproblem" and while reading $\S\ 8$ (his proof that computable numbers are enumerable) and his proof that ...
2
votes
1answer
64 views

Prove a set is not recursive / recursively enumerable

I have two sets B which is recursively enumerable and is not recursive, and A which is recursive. Is $A-B$ recursive and / or recursively enumerable? What about $B-A$? $B-A$ is obviously recursively ...
0
votes
1answer
16 views

complexity question regarding whether it is decision problem

When self teaching complexity theory and seeing arguments that were made online. I get some confusion. In the class, we classify problems into P: can be computed polynomially NP: given a claimed ...
1
vote
0answers
35 views

Find a $w$ such that $wxy = xyy$

Let $n,m \in \mathbb{N} \cup \{*\}$ and define $$nm = \begin{cases} \varphi_n(m) &\mbox{if } \varphi_n(m) \mbox{ converges} \\ * & \mbox{otherwise, including } * \in \{n,m\} \end{cases}$$ ...
1
vote
1answer
38 views

Is universality decidable?

Is there a turing machine which can take any other TM T as input and decide whether T is a universal turing machine?
1
vote
2answers
22 views

Question regarding the arithmetic hierarchy notation used in the corollary of Post's theorem

A set $B$ is $\Delta_{n+1}$ if and only if $B \leq_T \emptyset^{(n)}$. More generally, $B$ is $\Delta^C_{n+1}$ if and only if $B \leq_T C^{(n)}$. This is from ...
0
votes
1answer
55 views

Relationship between the Turing Machine and RAM Models

Could you tell me which is the relationship between the Turing Machine and RAM Models??
1
vote
1answer
40 views

Are these two notions of “computable function” the same or related?

From http://en.wikipedia.org/wiki/Semicomputable_function, we have: "If a partial function is both upper and lower semicomputable it is called computable." Is this the same kind of "computable ...
0
votes
0answers
18 views

exercise on recursion with partial function

Given g(x,y,z)= if (x=0) then y else z f1(t)= g(t,h(t),t) f2(t)= if (t=0) then h(t) else t where h(t) is a partial function, is it valid that ...
0
votes
1answer
31 views

Recursively enumerable sets: the halting set

Wikipedia on the Halting Problem: The conventional representation of decision problems is the set of objects possessing the property in question. The halting set $K := \{ (i, x) ~|~ \textrm{program ...
0
votes
0answers
11 views

Turing machine that modifies each cell that contains a certain input one time at most

If I have a single tape turing machine running on some input $x$, where it modifies each part of the tape with $x$ one time at most...would the TM be decidable? Any advice or guidance appreciated; ...
1
vote
2answers
36 views

What is effectively continuous?

In Soare's book Recursively Enumerable Sets and Degrees I saw a sentence: $\Phi_e$ is an effectively continuous functional from the Cantor space $2^\omega$ to itself. What does it mean for a ...
1
vote
1answer
27 views

Is it decidable that any two computable function over reals $ f(x_1,x_2,\dots,x_n)\equiv g(x_1,x_2,\dots,x_n)$

Is it decidable that any two computable function over reals or over sphere of complex $ f(x_1,x_2,\dots,x_n)\equiv g(x_1,x_2,\dots,x_n)$ ?
2
votes
1answer
41 views

Using the recursion theorem

The Recursion theorem states that if $f$ is a (total) computable function, then $f$ has a fixed point in the sense that there exists an $e$ such that $\varphi_e = \varphi_{f(e)}$. I have the following ...
2
votes
1answer
40 views

Are fixed-point combinators general recursive?

I'm not even sure if I'm asking the right way, but here's what I'd like to know: If your language has fixed-point combinators, is it automatically Turing complete?
0
votes
0answers
38 views

When can definite integration be numerically computable?

under what condition,can the integration $$\int_{\Delta}f(x_1,x_2,\dots,x_n)dx_1dx_2\dots dx_n, \text{where } \Delta \text{ is integration domain defined by function},f(x_1,x_2,\dots,x_n) \text{ ...
5
votes
2answers
212 views

Can it be decidable for any polynomials to have the intersecting point?

Give system of polynomials$$P_1(x_1,x_2,\dots,x_n)=0,$$$$\vdots,$$$$P_k(x_1,x_2,\dots,x_n)=0$$ Can it be decidable for thoses polynomials to have the intersecting point ?
0
votes
2answers
88 views

If all infinite r.e. languages have an infinite recursive subset, then do co-r.e. languages not have such subsets?

If all infinite r.e. languages have an infinite recursive subset, then can we take it to be true that co-r.e. languages do not have such subsets by complemence?
0
votes
1answer
41 views

Is the following statement true ? If $L$ is a decidable language and $L' \subseteq \; L$, then $L'$ is also decidable ? Prove your answer is correct [closed]

Is the following statement true ? If $L$ is a decidable language and $L' \subseteq \; L$, then $L'$ is also decidable ? Prove your answer is correct I can't figure out this question. Any tips ?
1
vote
1answer
48 views

Are well-orders of the same recursive length recursively isomorphic?

If the ordinal length of $A$ and $B$ is the same recursive ordinal, does it follow that there is a recursive one-one order-preserving correspondence between $A$ and $B$?
1
vote
0answers
39 views

How to find the shortest path of a graph in a turing machine

I'm reading about Turing machine and I saw some examples as: Let $M_{1}$ a Turing Machine and the language $B = \{w\#w \vert w \in \{0,1\}^{*}\}$, We want $M_{1}$ to accept if its input is a member of ...
1
vote
1answer
19 views

Computable function that enumerates the primitive recursive functions

I'm trying to construct a computable function $f:\omega^2\to\omega$ such that For all $e\in\omega$, $x\mapsto f(e,x)$ is primitive recursive. If $g:\omega\to\omega$ is primitive recursive, then ...
7
votes
0answers
115 views

Fixed points in computability and logic

I asked this question on CS.SE, too: http://cstheory.stackexchange.com/questions/27322/fixed-points-in-computability-and-logic I would like to understand better the relation between fixed point ...
4
votes
2answers
142 views

Is it possible to deduce Godel's first incompleteness theorem from Chaitin's incompleteness theorem?

I want to ask if it is possible to deduce Godel's first incompleteness theorem from Chaitin's incompleteness theorem. I am reading the following AMS-Notice article. The authors claim that: The ...
0
votes
1answer
127 views

Is Bell's Notion of “Abstract Set” Flawed?

Consider the following definition of "abstract set" given by John L. Bell (who wrote the book "Set Theory: Boolean-valued Models and Independence Proofs") from his preprint "Abstract and Variable ...
21
votes
5answers
2k views

Given any computable number, is there any algorithm to decide whether it is transcendental?

Given any computable number $a_c$, is there any algorithm to decide whether it is transcendental? Definition of “computable number”: According to Ming Li and Vitanyi, a real number $x=0.x_1x_2\ldots$ ...
2
votes
2answers
144 views

Different models of ZF disagree on equality of explicit recursively enumerable sets

Assuming that ZF is consistent, are there two recursively enumerable sets defined by explicit enumerators that are the same in one model of ZF+Con(ZF) but different in another model of ZF+Con(ZF)? If ...
2
votes
0answers
16 views

Kleene normal form : elementary?

The Kleene normal form explains there are primitive recursive functions $T$ (a predicate indeed) and $U$ such that for any computable function $\phi_n$, and for any $x\in\mathbb N$ : ...
0
votes
0answers
32 views

How to track unboundedly many changes?

Suppose that I have a piece of paper with 0 on it (and nothing else). Suppose that, at each instant, I can either replace what is on the paper by writing either 0 or 1. I say that I change the value ...
3
votes
0answers
82 views

Whats the connection between Turing machine and First order logic?

Today in my Computing class i came across the theorem which states that., If language $L$ and $\Sigma^*\setminus L$ are recursively enumerable then L is recursive (total turing machine). Which looks ...
1
vote
0answers
50 views

$n^{\text{th}}$ digit of $\sqrt{2}$ decimal representation is primitive recursive function

An exercise from Maltsev's "Algorithms and recursive functions". Problem: Let $\sqrt{2} = a_0,a_1a_2\dots a_n\dots$ be the decimal representation of $\sqrt{2}$. Show that the function $f(n) = a_n$ ...
0
votes
1answer
50 views

Partial / Total / Primitive recursive functions and recursive enumerability

After having compiled several sources from handbooks or the web, and read some answers posted here, I'm still confused with the question of non recursive enumerability of total recursive functions, ...
1
vote
0answers
23 views

Question about Computability

Q:Suppose $U(n,x)$ is Gödel Universal Function, show that there is $n$ such that $U(n,x)=n+x$ for all $x$ I did some proof but I am mot sure if I am right. Let's consider a computable binary function ...
0
votes
1answer
40 views

show that inverses $\pi_{1},\pi_{2}$ are recursive?

show that one can define inverses $\pi_{1},\pi_{2}$ for $ \langle.,.\rangle$ with$\pi_{1}(\langle m,n \rangle)=m,\pi_{2}(\langle m,n \rangle)=n\ \ \forall n,m$ wich are also recursive?
3
votes
1answer
41 views

Is there a recursive injective and surjective function f:N→PRF?

It is well known and easy to see that it is possible to effectively number Turing Machine codes. That is, there is an injective and surjective recursive mapping $g:\mathbb N\to {\rm TM}$: each Turing ...
1
vote
7answers
129 views

Text books on computability

I collected the following "top eight" text books on computability (in alphabetical order): Boolos et al., Computability and Logic Cooper, Computability Theory Davis, Computability and unsolvability ...
0
votes
0answers
28 views

It is undecidable if The Intersection between Context Free Language and Context Sensitive Language is the empty set

I'm trying to show that the following problem is undecidable: The intersection between a Context Free Language (CFL) and a Context Sensitive Language(CSL) is the empty set. I know that is undecidable ...
0
votes
1answer
27 views

Proving non-regularity of a language

How can I prove $L = (01^n2^n | n\geq 0)$ is not regular? Would it be sufficient to say that $01^p2^p$ is in $L$ and by pumping lemma, $01^p2^p$ can be written as $xyz$ such that $|y|>0, ...
3
votes
1answer
100 views

Undefinable Real Numbers

Disclamer: I'm sure my definition of "definable" may be different than the/a established mathematical one, I am more than interested in learning why/how this is so, but that is not my question Part ...
2
votes
1answer
33 views

Non-decidable $\Pi^0_1$ (effectively closed) classes

Are there non-decidable $\Pi^0_1$ (effectively closed) classes? According to a draft of Effectively closed sets by Cenzer and Remmel, the class $$ P = \{ 0^n1^\omega \mid n \in B\} $$ is a ...