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
votes
0answers
42 views

Algorithm to answer existential questions - Reduction

Lemma 1. For any $x$ in the ring $F[t,t^{-1}]$ ($F[t,t^{-1}]$: the polynomials in $t$ and $t^{-1}$ with coefficients in the field $F$), $x$ is a power of $t$ if and only if $x$ divides $1$ and ...
3
votes
0answers
26 views

FRACTRAN for natural numbers

Is there a simple analogue of FRACTRAN that maps a natural number to a natural number, instead of mapping a list of fractions to a natural number? One could use Gödel encoding to translate FRACTRAN ...
4
votes
1answer
110 views

The existential theory is undecidable

Lemma 1. For any $x$ in the ring $F[t,t^{-1}]$ ($F[t,t^{-1}]$: the polynomials in $t$ and $t^{-1}$ with coefficients in the field $F$), $x$ is a power of $t$ if and only if $x$ divides $1$ and ...
1
vote
1answer
38 views

Proof of a classical Theorem of Martin-Löf on complexity dips for Kolmogorov complexity,

I have a question on the first Theorem from the article Complexity of Oscillations in Infinite Binary Sequences by P. Martin-Löf, which could be downloaded from the publisher or from here. Theorem ...
2
votes
1answer
32 views

Intuition on Martin-Löf-Test for finite strings

The followng example is from An Introduction to Kolmogorov Complexity and Its Applications, Example 2.4.1. and is concerned with Martin-Löf-Tests for finite strings: A string $x_1 x_2 \ldots x_n$ ...
1
vote
1answer
27 views

Why $C(n\mid l(n)) \ge C(n) - C(l(n))$ for Kolmogorov complexity

Denote by $C(n)$ the plain Kolmogorov complexity of $n$ and the length of a binary encoding of $n$ by $l(n)$, why do we have $$ C(n\mid l(n)) \ge C(n) - C(l(n))? $$ If I have a shortest program $p$ ...
1
vote
0answers
12 views

Each recursive approximating sequence for Kolmogorov complexity is not uniform

Denote the plain Kolmogorov complexity by $C(x)$. Let $\phi(t,x)$ be a recursive function and $\lim_{t\to\infty} \phi(t,x) = C(x)$ for all $x$. For each $t$ define $\psi_t(x) := \phi(t,x)$ for all ...
2
votes
0answers
15 views

Kolmogorov complexity of substring if string is divided according to rule

Denote the plain Kolmogorov complexity of a string $u$ by $C(u)$. Now let $u$ be a string of length $n$ with $C(u) \ge n - O(1)$ and suppose $u = u_1 \cdots u_{\log n}$, a subdivision of the ...
3
votes
0answers
39 views

Induction Can't Prove Complexity?

Chaitin's incompleteness theorem says no sufficiently strong theory of arithmetic can prove $K(x) > L$ where $K(x)$ is the Kolmogorov complexity of natural number $x$ and $L$ is a sufficiently ...
1
vote
0answers
28 views

On Kolmogorov complexity of first and last half of a string

Denote by $C(x)$ the plain Kolmogorov complexity of $x$ and let $x$ satisfy $C(x) \ge n - O(1)$ with $n = |x|$. If $x = yz$ with $|y| = |z|$ show that $C(y), C(z) \ge n/2 - O(1)$. Any ideas how to ...
10
votes
1answer
129 views

Every non-increasing sequence of polynomial towers stabilizes — Finitary proof

In this question we are concerned only with positive integers $\mathbb N$ and other finitary objects that can be encoded using integers. A term function means a total computable function $\mathbb ...
1
vote
0answers
23 views

Kolmogorov complexity, no description mechanism can improve on additively optimal/universal one infinitely often

In An Introduction to Kolmogorov Complexity and Its Applications explaining the notion of additively optimal or universal it is written: The key point is not that the universal description method ...
2
votes
1answer
23 views

Relationship between computability and growth rate

Let $f:{\mathbb N}\to{\mathbb N}$ be an arbitrary function. Is there always a computable function $g:{\mathbb N}\to{\mathbb N}$ such that $g \geq f$ (i.e. $g(n)\geq f(n)$ for every $n$) ? The answer ...
9
votes
1answer
115 views

Non-computable function having computable values on a dense set of computable arguments

A rational complex number is a complex number whose both real and imaginary parts are rational numbers. Note that a rational complex number is a finitary object that can be an input or an output of an ...
2
votes
0answers
26 views

Decidability - Complexity

Can someone tell me where I can get some information about the following? We have linear differential equations with polynomial coefficients depending on x. $a_n(x)y^{(n)}+ \dots ...
-1
votes
0answers
29 views

Values of the Sudan function

I am talking about the first discovered recursive function which is not primitive recursive. I would like to know the exact values of $\ f(3,3,3), f(2,0,4), f(2,7,1), f(2,3,2)$ (where $f$ is the ...
3
votes
4answers
128 views

Where does this argument showing there are uncountably many TMs fail?

This argument comes up once every while on Lambda the Ultimate. I want to know where the flaw is. Take a countable number of TMs all generating different bitstreams. Construct a Cantor TM which runs ...
0
votes
2answers
20 views

Rice's Theorem when only finite number of instructions run

Rice's theorem says that there is no computable method F(m,p) to determine, if given as input a TM m, and some non-trival property p, if the language accepted by m has property p. To quote another ...
0
votes
1answer
31 views

Hardness of index sets for computable structures

Suppose we have a computable structure $M$ and we want to show that its index set $I(M)$ is (many-one) $\Gamma$-hard for some complexity class $\Gamma$ (like $\Sigma^0_2$). To do this, we need to show ...
3
votes
0answers
98 views

What does “Turing-complete” really mean?

People talk about various programming languages or computational models being "Turing-complete." But what does that technically mean? The technical definition is buried under tons of informal ...
2
votes
1answer
36 views

Why is $f(x)=x^{2}+1$ a primitive recursive function?

I'm trying to find out why $f:\mathbb{N}\rightarrow\mathbb{N},f(x)=x^{2}+1$ is a primitive recursive function. For $f(S(y))$ I can't seem to get it to fit the axioms known to me about primitive ...
6
votes
0answers
56 views

Primitive recursion and $\Delta^0_0$

Until recently I assumed that primitive recursive relations are exactly $\Delta^0_0$ (i.e. bounded) ones, but I learned they're different (the former is a proper superclass of the latter). I have ...
2
votes
1answer
62 views

Does semantic inconsistency guarantee syntactic inconsistency?

I'm wondering about the possibility of circumventing the problem of incompleteness posed by Roger Penrose in his book "Shadows of the Mind". It occurred to me (and, Googling has revealed to me, ...
0
votes
0answers
9 views

Generalizing equal turing machine problem

I know that $EQ_{TM} = \{<M_1,M_2> | L(M_1)=L(M_2)\} \notin RE \cup CO-RE$ Can I generalize and say that $L' = \{<M> | L(M) = C \} \notin RE \cup CO-RE$ Where C is the language of any ...
0
votes
0answers
9 views

Turing Machine Membership problem and how to prove its undecidable

ATM = {$<m, w>$ | M is a Turing Machine that accepts string w}. How can I prove that ATM is undecidable? Here's what I have so far: Any decidable problem is accepted by a Turing Machine. It ...
0
votes
0answers
13 views

Question about the effect of the basic primitive recursive projection function.

Projections are said to allow us to use "any argument in any order", and the function below can be proved to be a PR function by projections and the composition rule. Let $ i_0,\cdots,i_{m-1} \in n = ...
1
vote
1answer
52 views

What is the meaning of 'recursive' in Boolos, Burgess and Jeffreys? (Computability and Logic)

In the book Computability and Logic by Boolos, Burgess and Jeffrey (page 71 - 5th edition) it defines a recursive function as follows: The functions that can be obtained from the basic functions ...
0
votes
1answer
45 views

Unclear why (first order) satisfiability undecidable and not semi-decidable.

Hoping this will just be a terminology question, otherwise I have a bigger problem of harboring a misunderstanding re: decidability. We know that (first order) satisfiability (for the general case of ...
0
votes
0answers
32 views

What are non-monotonous computable convergent sequences of rationals with non-computable rate of convergence?

A computable convergent sequence of rationals can have a non-computable rate of convergence. By a rate of convergence of a sequence $(q_k)_k$, I mean a function $f : \omega \rightarrow \omega$ such ...
0
votes
0answers
35 views

How to predict intuitively the recurrence relations of josephus problem?

i have studied the Josephus problem from the concrete mathematics book.I have understand all related calculations discussed on that book.However i have some difficulties regarding to recurrence ...
2
votes
1answer
40 views

Understanding difference between reduction methods

In Sipser's book "Introduction to the theory of computation" there are 2 methods for proving that $\rm HALT_{TM}$ is undecidable by a reduction from $\rm A_{TM}$ I am trying to figure out the ...
0
votes
1answer
54 views

The result of substituting recursive total functions in a recursive relation.

In the book Computability and Logic by Boolos, Burgess and Jeffrey it defines a recursive function as follows: The functions that can be obtained from the basic functions $z, s, id^i_n$ by the ...
1
vote
1answer
35 views

A c.e. equivalence relation is computable if each equivalence class is of a fixed finite cardinality with finitely many exceptions

I've been working on the following quiz: Let $E \subseteq \omega \times \omega$ be a c.e. equivalence relation and $n \in \omega$. Suppose all of $E$'s equivalence classes but finitely many ...
0
votes
1answer
72 views

Computability problems — can't solve

I have a pair of exercises I can't solve (tomorrow I'll have a test). I need some kind of solution so I can apply it to other exercises...thanks to all! In the following $W_n$ means the domain of the ...
3
votes
2answers
76 views

Are untyped and simply typed lambda calculus mutually exclusive?

In "Proposition as Types" by Philip Wadler we can read that: The two applications of lambda calculus, to represent computation and to represent logic, are in a sense mutually exclusive. If ...
2
votes
1answer
42 views

Encode lambda calculus in arithmetic?

There is plenty of information about how to encode arithmetic given the lambda calculus. The wikipedia article on Church Encoding seems complete to my inexpert eye. My question is "how about the ...
13
votes
1answer
97 views

When is Chaitin's constant normal?

Chaitin's constant is not one constant, but depends on an effective prefix-free encoding $d$ of Turing machines as bit strings. Once such an encoding is chosen, the corresponding Chaitin's constant is ...
2
votes
2answers
62 views

Extended version of the theory of reals and its decidability

It is well-known due to Tarski that the theory of reals $(\mathbb{R},+,\cdot,<,=)$ is decidable. I was asking my self whether one would lose the decidability by adding all real constants. More ...
0
votes
0answers
11 views

Prove that $ALL_{CFG}$ is undecidable by reducing from PCP

I'm studying for a Computability exam that I have in a few weeks, and have come across this question which I'm having a hard time solving: Prove that $ALL_{CFG}=\left\{ \left\langle ...
9
votes
2answers
1k views

Show that the question “Is there life beyond earth?” is decidable

I was given a question to prove that there exists a turing machine that solves the question Is there life beyond earth? and is decidable. I actually don't understand how to show a turing ...
0
votes
1answer
79 views

Hanf Numbers and Decidability

Currently reading J.L. Bell's Models and Ultraproducts and at the end of Chapter 4 section 4 the authors comment that "In spite of the fact that most languages can easily be shown to possess Hanf ...
1
vote
1answer
49 views

Show $(\mathbb{Z}, +, \cdot, 1, 0 )$ is not R-decidable

Show $(\mathbb{Z}, +, \cdot, 1, 0 )$ is not R-decidable It gives the hint to use $x \in \mathbb{N} \leftrightarrow \exists x_0 \exists x_1 \exists x_2 \exists x_3(x \equiv x_0 \cdot x_0 \wedge x_1 ...
1
vote
2answers
47 views

show the set of valid second-order $\emptyset$-sentences is not R-enumerable

show the set of valid second-order $\emptyset$-sentences is not R-enumerable this would have the empty symbol set i.e. $S = \emptyset$ so it would be sentences that are universally or existentially ...
9
votes
0answers
170 views

The ethics of Borel determinacy

I was speaking with a friend the other day, and I happened to say "morally, Borel determinacy is as strong as ZF." I was riffing on the well-known result of Harvey Friedman, that we need ...
0
votes
2answers
56 views

Example of recursively enumerable languages that under intersection are $\emptyset$

I am trying to think about an example of a recursively enumerable languages $L_1,L_2 \in RE $ and $L_1,L_2 \notin R $ that satisfy: $L_1 \cap L_2 \in R $ I know that it will be probably something to ...
1
vote
2answers
42 views

Proving that $a \dot{-} (b+1) = (a \dot{-} b) \dot{-} 1$

This should be an easy exercise from Hodel's Introduction to Mathematical Logic, but for some reason I'm not getting it right. Define $a \dot{-} b$ as $a-b$ if $a \geq b$ and as $0$ otherwise. ...
1
vote
2answers
39 views

Little confused about the constraint of Injective Functions and Surjective.

From my understanding, A Function is called to be Injective, if different elements of the first set are mapped to different elements of the second set. Let set A = {a,b,c} and set B = {1,2,3} Are ...
1
vote
0answers
29 views

Is the computable numbers equal to the set of all the limits of finite length algebraic expressions?

Let's call $C$ the set of computable real numbers and $L$ the set of all the (existing) limits of finite length algebraic expressions. By $L$ I mean the set of all converging limits $\lim_{x_1 \to ...
4
votes
4answers
92 views

Why is the numbering of computable functions significant?

My course is about computability theory, and I'm having troubles with one of the main concepts. This might be a really newb question, but I've been struggling with understanding it's significance (and ...
7
votes
1answer
118 views

Comparing different relativizations in computability

Most, but not all, theorems in computability relativize. In principle, we should go through the original proof to check that a relativized version of a theorem holds. In practice, we often just wave ...