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)

7
votes
1answer
61 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
0answers
41 views

Diagonalization

So off and on I've been studying basic recursion theory and I've realized that, at least when restricted to the basic stuff I've been learning, recursion theory is essentially the study of uses of ...
1
vote
1answer
42 views

Example for 2 disjoint languages that cannot be separated by a decidable language

Question: Let A, B be languages such that A ∩ B = ∅. Say that a language C separates A and B if: A ⊆ C and B ⊆ $C^c$. Describe two languages A, B ∈ RE, that cannot be separated by any C, such that C ∈ ...
0
votes
0answers
12 views

program which it's power is equal to LBA

Can anyone give an opinion about this matter: what is the smallest program which it's power is equal to LBA Turing machine(Linear bounded automata are acceptors for the class of context-sensitive ...
2
votes
2answers
70 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
1answer
36 views

What is a simple proof that something is np complete that does not use np completeness of something else?

What is a simple proof that something is NP complete that does not use NP completeness of something else? Every proof seems to reduce to something else being NP complete.
2
votes
3answers
100 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 ...
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 ...
16
votes
4answers
2k views

Is chess Turing-complete?

Is there a set of rules that translates any program into a configuration of finite pieces on an infinite board, such that if black and white plays only legal moves, the game ends in finite time iff ...
4
votes
2answers
425 views

An “uncountable” Turing Machine?

A proof of the insolubility of the halting problem is a diagonalization, which I'm sure most of you have seen. I am not very familiar with set theory, but it strikes me as similar to Cantor's proof of ...
1
vote
2answers
42 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$ ...
8
votes
5answers
1k views

Example of a number that is not the limit of a computable sequence

Let's define a real number as computable iff there's an algorithm that can generate a sequence with the number as its limit (turing machine or any of the equivalent programming models). Not all real ...
1
vote
1answer
33 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 ...
1
vote
0answers
34 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) ...
6
votes
1answer
129 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
55 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
75 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
65 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
18 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 ...
3
votes
5answers
498 views

Recursion theory text, alternative to Soare

I want/need to learn some recursion theory, roughly equivalent to parts A and B of Soare's text. This covers "basic graduate material", up to Post's problem, oracle constructions, and the finite ...
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?
0
votes
1answer
56 views

Relationship between the Turing Machine and RAM Models

Could you tell me which is the relationship between the Turing Machine and RAM Models??
2
votes
2answers
359 views

Primitive recursive definition of the “divisibility” relation

Let $$d(x,y)= \begin{cases} 1, &\text{if }x\text{ is divisible by }y \\ 0, &\text{otherwise.} \end{cases}$$ How can I define $d(x,y)$ in terms of just the basic primitive recursive functions ...
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)$ ?
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 ...
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
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, ...
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 ...
0
votes
1answer
32 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 ...
2
votes
1answer
42 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?
5
votes
2answers
213 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
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{ ...
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
43 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
51 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$?
4
votes
2answers
147 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 ...
7
votes
0answers
118 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 ...
1
vote
0answers
40 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 ...
0
votes
1answer
21 views

What do $A \upharpoonright x$ and $\mu s \ge x$ denote?

I am reading Computability Theory by Cooper and I do not understand the notation in the definition on the page 230: Let $\{A^s\}_{s \ge 0}$ be a $\Delta_2$-approximating sequence for $A \in ...
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 ...
6
votes
1answer
87 views

Who first discovered that some R.E. sets are not recursive?

Who first discovered that some recursively enumerable sets are not recursive, or equivalently that some semidecidable sets are undecidable? And in what context? Was the earliest formulation of this ...
0
votes
1answer
128 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
145 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
17 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$ : ...
3
votes
0answers
83 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 ...