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)

0
votes
1answer
41 views
+100

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
0answers
32 views

Show that all recursively enumerable sets are definable in arithmetic [on hold]

This is taken to be a given in most proofs and textbooks - can somebody prove this. Thanks
2
votes
2answers
348 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
25 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
21 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
38 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
17 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
28 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
26 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
34 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
38 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
205 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
35 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
83 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
35 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
43 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
123 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
102 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
37 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
18 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
85 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
126 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
140 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$ : ...
3
votes
0answers
80 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 ...
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 ...
1
vote
7answers
124 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
1answer
45 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
47 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
0answers
11 views

Compute the composition of functions

I got wrong in this very odd question for my assignment. Can somebody help me with the answer of this question provided an explantion? Thank you a lot in advance!
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
39 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 ...
0
votes
0answers
24 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 ...
3
votes
0answers
111 views

indices set and halting problem in computation course

I ran into a multiple choice question that confused me with this notation. anyone could help me? this is adapted from an old class quiz in Calgary. Suppose A is be indices (i think index set) of type ...
0
votes
2answers
86 views

Input and output of a Turing machine

For some machine models of computation there is no question what their input and output is: it's just the contents of some specific "cells", e.g. on a "tape" isomorphic to $\mathbb{N}$. Consider for ...
4
votes
1answer
279 views

Are continuous chaotic systems necessarily uncomputable?

I have seen the claim in a recent unpublished paper that chaotic dynamics are necessarily uncomputable. This follows, they argue, from the sensitivity to initial conditions shown in chaotic systems. ...
3
votes
1answer
98 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 ...
6
votes
0answers
82 views

Challenge on Some Definition on Formal Language & Recursive & Automata

We know set A is countable if A is finite or in a one-to-one mapping to natural numbers. Suppose $\Sigma$ be an arbitrary finite alphabet. I summarize my inference: a) Each arbitrary Language on ...
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 ...
0
votes
0answers
37 views

Proving the intersection and union of two simple sets is simple.

Question: Suppose $A$ and $B$ are simple. Prove that $A \cap B$ is simple and $A \cup B$ is either simple or cofinite. I need to verify that $A \cap B$ and $A \cup B$ are computably enumerable ...
1
vote
1answer
28 views

Gathering nonconsecutive 1's by a Turing machine

S. Barry Cooper comments his output convention for $\mathbb{N}\rightarrow\mathbb{N}$ Turing machines like this: Outputting $n$ as $n$ possibly nonconsecutive $1$'s is very natural. [...] We can ...
0
votes
0answers
43 views

Existence of a basis in constructive vector spaces

As I was trying to review forgotten knowledge on Vector Spaces in wikipedia, I read that the existence of a basis follows from Zorn lemma, hence equivalently from the axiom of choice. Actually, the ...
1
vote
1answer
28 views

Show that whether or not an arbitrary Turing machine ever executes a particular one of its instructions is unsolvable

Show that whether or not an arbitrary Turing machine ever executes a particular one of its instructions is unsolvable. (This is the same as the problem of detecting unreachable code in a program.)
0
votes
1answer
34 views

What mathematical structure best entails self-modifying programs?

If a program description can be represented as a sequence, then what is the best structure to entail program descriptions which self-modify? There must exist a relationship between the structure in ...
1
vote
0answers
42 views

An algorithmic approach to constructing the real numbers

To specify a real number, we can describe a rule which, given any rational number, tells you whether it's Too Big or Too Small. The rule should be self-consistent, in the sense that if $a$ is Too Big ...