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

When is a Decidable Set Decidable?

Can the same set be decidable in a strong theory and undecidable in a weaker theory? Some possible examples. Goodstein's theorem says every Goodstein sequence, $g(n)$, eventually terminates. ...
0
votes
0answers
88 views

A is recursive iff A is the range of an increasing function which is recursive

Working a problem stated in Enderton, but stated better and apparently stronger in Soare. All citations hereon are for Soare (1987). Would appreciate help on the proof. I know there has to be a more ...
4
votes
2answers
85 views

Showing that a function is not computable.

the following function was shown not to be computable: $h(x) = \begin{cases} \mu n.\Phi_x(n) \downarrow & \mbox{if } \exists n \Phi_x(n) \downarrow \\ \uparrow & \mbox{otherwise} \end{cases}$ ...
1
vote
0answers
75 views

A turing machine which computes the same language as a “stay put” turing machine

Im not sure I really understand how stay put machines work. I know they are just like turing machines but with states. So they can "stay put". But what confuses me is when you define a FSA for a ...
0
votes
1answer
44 views

Polytime implementation of Discrete Log using primitive recursive functions

The primitive recursive functions are defined by Godel as: $z() = 0$ $s(x) = x+1$ $\pi_i(x_1, \dots, x_k) = x_i$ Plus closure under Composition: $h(x_1, \dots, x_m) = f(g_1(x_1, \dots, x_m), ...
7
votes
2answers
277 views

Existence of a utility function on the reals

Suppose I have $\preceq$, a total order on $\mathbb R^n$. I wish to show that there is a utility function $u:\mathbb R^n\to\mathbb R$ such that $x\preceq y \leftrightarrow u(x)\leq u(y)$. I came up ...
1
vote
2answers
65 views

Decidability of Recursively Enumerable Languages

I'm having trouble with this problem, I know that every decidable language is recursively enumerable but that not every recursively enumerable language is decidable. What are the steps involved in ...
2
votes
1answer
37 views

if I find a bijection, rather than it is computable or not even computable, then the set would be denumerable or not?

In "Computability: an introduction to recursive function theory", by Cutland, there is a theorem as follows: Theorem 2.4 $\mathcal{C}_n$ is denumerable. where $\mathcal{C}_n$ represents the set of ...
1
vote
1answer
39 views

Kolmogorov (Kolmogoroff- ) Complexity of infinite sequences, Request for Proof

Let $\xi \in X^{\omega}$ be an infinite sequence and denote by $\xi[1\ldots n]$ its length $n$ initial segment. Then (due to Martin-Löf) the following holds: For every $\xi \in X^{\omega}$ there ...
1
vote
1answer
28 views

Constructing function for set enumeration

Let $X$ be a set non-negative integers. Let $X^i$ denote $i$-th cartesian power of set $X$. Let $X^* = \bigcup\limits_{i=1}^\inf X^i$, i.e. all possible combinations of $X$'s elements. Let ...
1
vote
1answer
31 views

Direct proof that $K \leq_\mathrm{T} Rec$

Soare's Recursively Enumerable Sets and Degrees (1987) shows that $Rec = \left\{ e : W_e \text{ is recursive} \right\}$ is $\Sigma^0_3$-complete via its relationship to other index sets, namely $Cof$ ...
1
vote
1answer
62 views

Show that the Turing machine will solve the self-halting problem

Suppose we have Turing machine $M^*$ that: i. halts printing 1 if $M_n$ halts on input 1 ii. halts printing 0 if $M_n$ doesn't halt on input 1 Show that you cannot construct $M^*$. ...
0
votes
3answers
38 views

Figuring out the steps in a Recursive Function

I have the following recursive function: $f(0) = 7$ $f(n+1) = f(n) + 6n + 1$ for all integers $n => 0 $ I know the answer is $f(n) = 3n^2 + 2n + 7$ I would like to know the steps to get to this ...
0
votes
1answer
37 views

Kolmogorov (Kolmogoroff-) Complexity, Contradiction with Invariance Theorem.

Fix some programming languages $S$ which is rich enough such that one can write interpreters for $S$ in $S$. Define $$ K(w) := \mbox{length of a shortest program producing $w$}. $$ Now fix some ...
7
votes
1answer
114 views

Proof-theoretic characterization of the primitive recursive functions?

The total recursive functions are exactly those number-theoretic functions that can be represented by a $\Sigma_1$ formula of first-order arithmetic. Is there a similar characterization of the ...
0
votes
1answer
107 views

Show that $gcd(x,y)$ and $z = lcm(x,y)$ is primitive recursive

For the $gcd(x,y)$ we note: $gcd(x,0) = x$ $gcd(x,succ(y)) = gcd(succ(y),mod(x,succ(y)))$ $succ(x)$ and $mod(x,y)$ are both primitive recursive, so $gcd(x,y)$ must be as well. $z = lcm(x,y)$ if ...
1
vote
3answers
70 views

How does one generally use partial function in logical statements?

How does one generally use partial function in logical statements? How it's done in practice? Specifically, let $M$ by a Turing machine, $f_M:\{0,1\}^*\to\{0,1\}$ the characteristic function which ...
1
vote
1answer
78 views

Problem from Cutland's Computability: 3.2. problem 3

The problem goes as follows. Let f: N --> N, such that f is partial, N is the natural numbers, and let m $\in$ N. Construct a non-computable function g such that g(x) = f(x) for x$\le$m. Proof: By ...
0
votes
2answers
55 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
73 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
38 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
51 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
49 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 ...
19
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 ...
0
votes
0answers
238 views

A turing machine for binary addition

How would I write a turing machine which has configurations which does 2 bit binary addition?
14
votes
3answers
325 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 ...
9
votes
1answer
169 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
55 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
143 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 ...
7
votes
0answers
120 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
39 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
271 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
139 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
70 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
54 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
57 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
45 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
67 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
57 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
51 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
88 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
144 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
126 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
50 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
195 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
39 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
145 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
57 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 ...