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
vote
1answer
61 views

Most “simple” $\mu$-recursive function that is not primitive recursive

Maybe the most prominent example of a $\mu$-recursive function that is not primitive recursive is the Ackermann function. But writing it out as a $\mu$-recursive function ("breaking it all the way ...
0
votes
1answer
32 views

Currying syntax clarification - how to work through an example of currying?

I understand currying from a computer science background, so I'm happy explaining currying with a before and after example in specific languages, eg, in Java ...
1
vote
1answer
71 views

Why are all computable functions representable in PA?

I'm trying to understand the proof of the first incompleteness theorem, and more specifically, the diagonal lemma. Suppose $GN(x)$ is the Gödel Number of a formula $x$. The first step of the diagonal ...
2
votes
0answers
30 views

Computability of determining whether an expression equals zero

Suppose we are given an expression composed of integers,$ +, *, -, /,$ elementary functions $(exp, sin, cos, tan)$ and their inverses (and for simplicity, assume each argument to these functions is in ...
3
votes
1answer
54 views

Is there an incomplete Turing degree that is not r.e.?

$\exists A \in \mathcal{P}(\mathbb{N}). (A \lt_T 0' \land \neg \exists B \in \Sigma_1. A \equiv_T B)$? In words: does there exist a subset of natural numbers that is Turing reducible to the halting ...
1
vote
1answer
49 views

two way infinite turing machine?

A Single tape turing machine is generally unbounded to right and starts from left. Read/write head moves to right from left after consuming a symbol. But what if we make left side unbounded too and ...
22
votes
8answers
3k views

There is a subset of positive integers which no computer program can print

It's said that a computer program "prints" a set A ($A \subset \mathbb N$, positive integers.) if it prints every element in A in ascending order (Even if A is infinite.). For example, the program can ...
0
votes
1answer
188 views

True or false? If $\eta$ is an explicitly defined incomputable number, then no formal system can pin down the value $\eta$ to arbitrary precision.

Let $\eta$ denote an explicitly defined incomputable real number (the bounty text is faulty, and does not mention incomputability of $\eta$). Then I think that no (recursively ennumerable) formal ...
0
votes
0answers
57 views

Well defined uncomputable numbers.

For any prefix-free universal computable function $F$ with domain $P_F$, the Chaitin’s constant $$ \Omega_F=\sum_{p\in P_F}2^{-|p|} $$ is a number $\in [0,1]$ and seems "well defined". But this ...
3
votes
1answer
86 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 ...
0
votes
0answers
22 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 ...
1
vote
1answer
86 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 ∈ ...
2
votes
1answer
51 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
2answers
84 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
163 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
48 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$ ...
7
votes
1answer
96 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
64 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
182 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
77 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
165 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
69 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
82 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
109 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
21 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
45 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
48 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
28 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
149 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
48 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
1answer
56 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 ...
1
vote
2answers
41 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
34 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
55 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
45 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
45 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
218 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
120 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
57 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
56 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$?
2
votes
0answers
66 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
39 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
189 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
240 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
158 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 ...
22
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$ ...
3
votes
2answers
165 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
40 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$ : ...
1
vote
0answers
39 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
138 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 ...