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
2answers
56 views

Understanding second axiom of Primitive recursion

I read about Primitive recursion and was able to understand most of it. However I am finding it very difficult to understand the second axiom of primitive recursion. I can make out that it helps in ...
0
votes
1answer
79 views

Complexity of Recursively Inseparable Sets

I am interested in examples of recursively inseparable sets. A standard example is the set of positive integers encoding a Turing machine that halts in an odd number of steps on blank input versus ...
1
vote
1answer
44 views

Function composition in computability

I have been reading Cutland's computability book, which is really good! However, I have found myself thinking way too much about one little passage in the the third section of the second chapter (the ...
0
votes
3answers
56 views

A multivariate function, computable for any fixed first argument, is computable

Claim: If $f:\mathbb N^{k+1}\to\mathbb N$ is a function such that for all $x_0\in\mathbb N$, $\lambda x_1,\dots,x_k.f(x_0,x_1,\dots x_k)$ is a partial recursive function then $f$ is also partial ...
1
vote
1answer
52 views

Non-computable c.e. sets are Kurtz random

I'm trying to directly show that non-computable c.e. sets are Kurtz random, without using the concept of genericity, but to little success. I assume by way of contradiction that $\emptyset'$ (for ...
2
votes
1answer
52 views

The “computability” of fundamental physical constants

I would like to ask if any of the fundamental physical quantities like the speed of light or plancks constant (all measured according to a common standard of of units) can be classified as computable ...
20
votes
2answers
2k views

Are transcendental numbers computable?

Wikipedia states: "The computable numbers include many of the specific real numbers which appear in practice, including all real algebraic numbers, as well as e, π, and many other transcendental ...
15
votes
3answers
368 views

Mathematical Notation and its importance

You can see how mathematical notation evolved during the last centuries here. I think everyone here knows that a bad notation can change an otherwise elementar problem into a difficult problem. Just ...
10
votes
1answer
182 views

A result of van der Waerden says Galois theory “needs” incomputable sets - what does this mean, exactly?

I happened across the recent arXiv paper Transfinite Recursion In Higher Reverse Mathematics, and the introduction begins: The question "What role do incomputable sets play in mathematics?" has ...
1
vote
2answers
62 views

Why is the set of formal propositions enumerable?

Thanks for your reading, A set S is recursively enumerable if one can write a program such that, once the program is launched, it will print a list of elements of S and, for all elements s ∈ S , the ...
11
votes
1answer
147 views

Consistency strength of Turing measurability

This is probably well-known to recursion theorists, but as google didn't help me, I'll ask it here. Convention: All sets of reals in the following discussion are assumed to be closed under Turing ...
8
votes
0answers
125 views

Elementary references on Robinson Arithmetic, Prim. Recursive fns etc.

I'm in the middle of revising my freely available and much-downloaded introductory notes Gödel Without (Too Many) Tears. (They are a sort of cut down version of part of my Gödel book, and I'm ...
0
votes
1answer
42 views

Are these sets recursive, r.e. or none

Are the sets a) $\{x | \exists y \phi_x(y) = 0\}$ b) $\{x | \phi_x(5) \uparrow \land x \leq 5\}$ recursive, recursively enumerable (r.e.) or none of them? Please explain your solution. $\phi_x$ ...
4
votes
1answer
281 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. ...
13
votes
1answer
148 views

Tennenbaum's theorem without overspill

While trying to clean up Wikipedia's proof sketch for Tennenbaum's theorem (there is no computable non-standard model of Peano Arithmetic), the following strategy occurred to me. Since it seems to be ...
2
votes
2answers
77 views

Can we find a formula defining a recursively enumerable set?

By Post's Theorem we know that a set $A\subseteq\mathbf{N}$ is recursively enumerable iff it is definable by a $\Sigma_1$-formula, i.e. there exists a $\Sigma_1$-formula $\varphi(x)$ with $x$ free ...
1
vote
2answers
55 views

Reduction between two languages and a common one

My question is as following : Let $A$ and $B$ be some languages, there exist a language $C$ such that $A\le C$ and $B\le C$, where "$\le$" means "reducible to", so $A\le C$ means there is a mapping ...
3
votes
1answer
60 views

Structure of partial recursive function over recursively enumerable guard

I read that the function $$ f(n) = \left\{ \begin{array}{l l} g(n) & \quad \text{if $n \in A$}\\ \text{undefined} & \quad \text{otherwise} \end{array} \right. $$ is recursive if ...
1
vote
1answer
50 views

Complexity class with arithmetical oracle.

Although I feel the answer to the following question is negative, I can't get any precise results neither find anything to read. The question is: Would a complete oracle from some level of ...
3
votes
1answer
68 views

Computably enumerable sets are not algorithmically random

I am informed that no computably enumerable sets are algorithmically random. I tried to show it by constructing an ML test, and looked up the proof in Downey & Hirschfeldt, but in vain. I would ...
2
votes
1answer
58 views

Determining if a theory in first-order logic is decidable

We have a theory in first-order logic which we know that is uncountably categorical, complete but not finitely axiomatisable. We also want to know if it is decidable. But I don't know the procedure ...
2
votes
1answer
52 views

Steps for applying Rice's theorem to any sets

I know that this set: $$\{i\ |\ \ \phi_i(n) \text{ converges } \}$$ is not recursive and that this can be shown by Rice's theorem. But everywhere I look i just found that it's not recursive ...
0
votes
1answer
91 views

Proving sets to be (not) recursive or r.e.

I am stuck proving the following sets to be recursive or recursive enumerable (or none of the both). first set: $$\{i\ |\ \exists n, \phi_i(n) \text{ converges and } \phi_i(n+1) \text{ converges}\}$$ ...
2
votes
1answer
147 views

Subsets of all Diophantine's sets

Function $\mathbb{N}^k \to \mathbb{N}^m$ is computable $\Leftrightarrow$ graph of function is Diophantine. Consider some subset $S$ of computable functions (for example some Grzegorczyk's class or ...
3
votes
3answers
133 views

Is it possible to create a string with known Kolmogorov Complexity?

I wish to compare compressors using strings with known Kolmogorov Complexity, but I haven't got the theoretical background and tools to understand how to do that. I'm just starting in this area and ...
1
vote
2answers
52 views

The universal turing relation

I'm just starting to learn computability. Some treatments of the subject use a relation they call $T$, which I think is called the universal recursive relation. It's defined something like this ...
0
votes
1answer
80 views

Prove that there exists an index for a specific computable function

How can I prove that there exists an index $x$ s.t. the $x$-th computable function(0) $= x^2$ Thank you
3
votes
1answer
198 views

Are there more true statements than false ones?

Let us enumerate all statements of PA or ZFC by length, upto n characters, then in the limit as $n\rightarrow\infty$, what proportion of statements are provably true, provably false, or independent? ...
0
votes
1answer
40 views

classifying problems with reducibility

How can we use a reduction to prove non membership of a class. Can we say if A is reducible to B they are in same class or if we can't reduce A to B. B is not same class as A. Regards,
4
votes
2answers
147 views

About theorem's proof length in propositional calculus

In PC(propositional calculus) system, how long will a formula's proof be? That is to say if there exists a computable function $f$ such that for any formula $A$, if $\vdash_{\mathrm{PC}}A$ then $A$ ...
3
votes
3answers
62 views

noncomputable functions

I know that there exist functions such that no computer program can, given arbitrary input, produce the correct function value. There is nothing, however which would prohibit us from knowing the ...
3
votes
1answer
68 views

Construction of a Kurtz random sequence that's not Martin-Löf random

How can one construct a Kurtz random sequence that's not Martin-Löf random? I'm also interested in the paper that included the first of such constructions. I suspect it was in Kurtz's dissertation, ...
1
vote
1answer
86 views

Solving the halting problem for *almost* all machines?

As I understand it, the proof of the halting problem’s undecidability is conceptually pretty simple. You postulate a machine $h(m, x)$ which (1) always halts and (2) returns 1 if $m$ halts with input ...
2
votes
0answers
72 views

Check that constructed recursive function proves that set is recursive.

Let $\forall\exists$-formula be any formula that looks like $\forall x_1...\forall x_m$$\exists y_1...\exists y_n \phi$, where $x_1...x_m, y_1...y_n$ - variables, $m,n \ge 0$ , $\phi$ - unquantified. ...
0
votes
1answer
44 views

quick guide to understand theory of computation

Can someone tell me some quick guides in understanding theory of computation. I know this is not the place to ask such question
1
vote
1answer
47 views

two Creative and Productive sets

I am studying CUTLAND "Computability-An introduction to recursive function theory" book. In this book two sets are introduced: $$ Z = \{x| \phi_x(x)=0\} $$ $$ R=\{x|\phi_x=0\} $$ the set $ \ Z $ ...
4
votes
1answer
83 views

Is the ordinal $\omega \uparrow^\omega \omega$ still recursive?

In this question, a very large countable ordinal $\omega \uparrow^\omega \omega$ is defined. Is this ordinal still recursive?
1
vote
1answer
82 views

A non-r.e. language whose complement is not r.e.

What's an example of a language that is not recursively enumerable and whose complement is also not recursively enumerable?
1
vote
1answer
42 views

Construction of a universal prefix-free Turing machine

How can one construct a universal prefix-free Turing machine (TM)? By a universal prefix-free TM, I mean a prefix-free TM $U$ (that is, a TM whose domain is prefix-free) such that for every ...
1
vote
1answer
65 views

Undecidability of a Formal Language

I want to show that the following language is undecidable. Please help me verify the correctness of my solution. Thanks in advance! \begin{equation} ...
3
votes
1answer
45 views

Mapping reduction to show NeverHalt is undecidable

I need help with showing that $NeverHalt_{TM} = \{\langle M\rangle|M\text{ is a TM which runs forever on every input $w$}\}$ is undecidable by giving an explicit mapping reduction. To show that a ...
1
vote
2answers
73 views

Enumerable and not enumerable sets

I am i bit stuck on this problem. Is it possible that sets A and B are not enumerable, but set $$A \cdot B =\{x \cdot y \mid x \in A, y \in B\}$$ is enumerable? Defenition of emumerable set so, set ...
2
votes
1answer
66 views

Possible Turing degrees of countable models of ZFC

Let $M$ be a countable model in a signature $\Sigma$. We assume $\Sigma$ is finite, and (for convenience) has no function or constant symbols. Without loss of generality, we can assume that $M$'s ...
0
votes
1answer
65 views

A setting in which Rice's theorem is not true

In my class we call a set of computable functions $A$ recursive if its indexing set $I_A=\{e\in\mathbb N:\phi_e\in A \}$ is recursive, where $\phi$ is some known Gödel numbering of the computable ...
6
votes
1answer
188 views

How many busy beavers with the same number of states

Can the number of busy beavers with n states be computed, or would it be necessary to analyze all the machines to count them ?
1
vote
0answers
93 views

Oracle Turing machine - $E_{\text{TM}}$ and $PCP$.

$$E_{\text{TM}}=\{\langle M\rangle|M\text{ is a TM and $L(M)=\emptyset$}\}.$$ $E_{\text{TM}}$ is undecidable $$PCP=\{\langle P\rangle|P\text{ is an instance of the Post Correspondence Problem with a ...
0
votes
2answers
113 views

An effective enumeration of recursive sets in increasing order

Definition: We call a set recursive if its characteristic function is recursive. Claim: If the set $A\subset\mathbb N$ is recursive then $A=Range(f)$ for some recursive and increasing function. ...
1
vote
1answer
194 views

All infinite recursive sets can be enumerated by an injective function

Definition: We call a set recursive if its characteristic function is recursive. Claim: If the recursive set $A\subset\mathbb N$ is infinite then $A=Range(f)$ for some primitive recursive injective ...
2
votes
1answer
69 views

Reducing A$_\text{TM}$ to REGULAR$_\text{TM}$

We can solve A$_\text{TM}$ problem using REGULAR$_\text{TM}$. Assume $R$ is a Turing machine that decides REGULAR$_\text{TM}$. We construct $S$ to decide A$_\text{TM}$ as follows On input ...
0
votes
1answer
56 views

Prove that [x/y] is a primitive recursive function

Prove that [x/y] is a primitive recursive function using this theorem: If $g(x_1,...,x_n)$ is primitive recursive, then $f(x_1,...,x_n)=\sum^{x_n}_{i=0}g(x_1,...,x_{n-1},i)$ is also a primitive ...