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)

23
votes
5answers
3k views

Are some real numbers “uncomputable”?

Is there an algorithm to calculate any real number. I mean given $a \in \mathbb{R}$ is there an algorithm to calculate $a$ at any degree of accuracy ? I read somewhere (I cannot find the paper) that ...
14
votes
3answers
2k views

Are there any examples of non-computable real numbers?

Is this true, that if we can describe any (real) number somehow, then it is computable? For example, $\pi$ is computable although it is irrational, i.e. endless decimal fraction. It was just a luck, ...
16
votes
5answers
2k views

Is it possible to solve any Euclidean geometry problem using a computer?

By "problem", I mean a high-school type geometry problem. If no, is there other set of axioms that allows that? If yes, are there any software that does that? I did a search, but was not able to ...
4
votes
1answer
281 views

Show $f$ is primitive recursive, where $f(n) = 1$ if the decimal expansion of $\pi$ contains $n$ consecutive $5$'s

Let $f:\mathbb{N}\to\mathbb{N}$ be given by $f(n)=1$ if the decimal expansion of $\pi$ contains $n$ consecutive $5$'s, and $f(n)=0$ otherwise. How would you go about showing such a function is ...
0
votes
1answer
28 views

Any problem computable in $k$ memory slots can be computed with polynomials.

Let our memory slots be represented by elements of $\Bbb{Z}_p$ for a prime $p$. $k$ memory slots would be $k$ copies of the ring: $R = (\Bbb{Z}_p)^k$. Suppose that for a problem $f : X \to Y$, ...
13
votes
6answers
2k views

What philosophical consequence of Goedel's incompleteness theorems?

I want to write a philosophical essay centered about Goedel's incompleteness theorem. However I cannot find any real philosophical consequences that I can write more than half a page about. I read the ...
6
votes
1answer
361 views

Is there an infinite set of strings whose Kolmogorov complexities are computable?

Is there an infinite set of strings whose Kolmogorov complexities are computable?
2
votes
4answers
2k views

Example of a not recursively enumerable set $A \subseteq \mathbb{N}$

Can someone give me an example if a not recursively enumerable set $A \subseteq \mathbb{N}$ ? I came up with this question, when trying to show, that there exist partial functions $f: \mathbb{N} ...
0
votes
2answers
280 views

Index set definition in Computation Theory

We know index set is a set of all indices of some family of computable [partial] functions/computably enumerable sets. The empty set is a set of computable functions, and the empty set is ...
17
votes
3answers
816 views

Is the Collatz conjecture in $\Sigma_1 / \Pi_1$?

Prompted by some of the comments on this question, I'm wondering if anything is known about the place of the Collatz Conjecture in the arithmetic hierarchy. More specifically, is Collatz known to be ...
4
votes
1answer
398 views

Why doesn't diagonalization prove that integers are not countable?

I understand how Cantor's diagonalization argument works with respect to disproving that a bijection between integers and real numbers can exist. What I don't get is why the same reasoning doesn't ...
3
votes
3answers
799 views

Is the language of all strings over the alphabet “a,b,c” with the same number of substrings “ab” & “ba” regular?

Is the language of all strings over the alphabet "a,b,c" with the same number of substrings "ab" & "ba" regular? I believe the answer is NO, but it is hard to make a formal demonstration of it, ...
2
votes
1answer
261 views

Restricted read twice BDDs and context free grammars

Several papers give poly-time algorithms for constrained paths on labelled graphs, e.g. [1] Quote: Given an alphabet Σ, a (directed) graph G whose edges are weighted and Σ-labeled, and a formal ...
1
vote
1answer
165 views

Recursive relation and predicate

If we let P(x,y) be a primitive recursive relation and g(x) be a primitive recursive function. Then how to show that there exists a y < g(x)*P(x,y) is a primitive recursive relation? And how can ...
3
votes
1answer
152 views

Why do $\omega$-models of subsystems of $\mathsf{Z}_2$ satisfy full induction?

Richard Shore, in his 2010 paper in the Bulletin of Symbolic Logic, 'Reverse Mathematics: The Playground of Logic', writes that Obviously, if an $\omega$-model $\mathcal{M}$ (those with $M = ...
1
vote
1answer
307 views

Converse of Collatz Conjecture

How to write a pseudocode program that halts only if the Collatz Conjecture is false. Thanks much in advance!!!
0
votes
1answer
75 views

is differ between distributive lattice vs semi-lattice on Turing Degrees

We know a Posed Closed under suprema but not necessarily under infima is an upper semi-lattice. We now r.e set forms a distributive lattice. But my question is why following statement is hold? I ...
0
votes
0answers
120 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 ...
0
votes
1answer
227 views

Simultaneous recursion

I have no idea how to even start proving the following theorem: If $f_0, f_1: \mathbb{N}^r \rightarrow \mathbb{N}$ and $g_0, g_1: \mathbb{N}^{r+3} \rightarrow \mathbb{N}$ are primitive recursive, ...
-2
votes
1answer
98 views

Why is $x\mapsto x$-th prime number a partial recursive function?

I think that partial recursive functions correspond to all computable functions. Thus, if we can write a computer program to represent a function, the function is partial recursive. In computability ...
28
votes
4answers
915 views

Why do we believe the Church-Turing Thesis?

The Church-Turing Thesis, which says that the Turing Machine model is at least as powerful as any computer that can be built in practice, seems to be pretty unquestioningly accepted in my exposure to ...
17
votes
2answers
2k views

Density of halting Turing machines

If we enumerate all Turing machines, $T_1$, $T_2$, $T_3,\ldots,T_n,\ldots$, What is $$\lim_{m\to\infty}\frac{\#\{k\mid k\lt m \text{ and }T_k\text{ halts}\}}{m}\quad?$$ Or does this depend on how we ...
8
votes
1answer
432 views

Irrationality measure of the Chaitin's constant $\Omega$

What is known about irrationality measure of the Chaitin's constant $\Omega$? Is it finite? Can it be a computable number? Can it be $2$?
8
votes
4answers
487 views

Consequences of solving the Halting problem

What impact would a device (ie super-computer or relativistic computer or other method) that solves the halting problem have on math? Would there be any mathematical problems left to solve? What ...
15
votes
3answers
540 views

How can Busy beaver($10 \uparrow \uparrow 10$) have no provable upper bound?

This wikipedia article claims that the number of steps for a $10 \uparrow \uparrow 10$ state (halting) Turing Machine to halt has no provable upper bound: "... in the context of ordinary ...
11
votes
1answer
12k views

Recognizable vs Decidable

What is difference between "recognizable" and "decidable" in context of Turing machines?
7
votes
3answers
1k views

Prove Gödel's incompleteness theorem using halting problem

How can you prove Gödel's incompleteness theorem from the halting problem? Is it really possible to prove the full theorem? If so, what are the differences between original proof and proof by ...
6
votes
1answer
93 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 ...
5
votes
5answers
697 views

Can a polynomial size CFG over large alphabet describe a language, where each terminal appears even number of times?

Can a CFG over large alphabet describe a language, where each terminal appears even number of times? If yes, would the Chomsky Normal Form be polynomial in |Σ| ? EDIT: What about a language where ...
8
votes
2answers
320 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 ...
7
votes
1answer
208 views

Primitive recursive function which isn't $\Delta_0$

What is the simplest/cutest example (and/or example with the most student-friendly proof that it is an example) of a primitive recursive function which isn't representable by a $\Delta_0$ wff?
6
votes
1answer
373 views

What are $\Sigma _n^i$, $\Pi _n^i$ and $\Delta _n^i$?

Sometimes reading on wikipedia or in this site (and in very different context like topology, arithmetic and logic) I have found these symbols $\Sigma _n^i$, $\Pi _n^i$ and $\Delta _n^i$. They are ...
5
votes
3answers
289 views

Numbers which are “Provably Difficult to Compute”?

We recall that a computable number $\alpha \in \mathbb{R}$ satisfies the following: there exists a computable function $f$ such that, given any positive rational error bound, $f$ outputs a rational ...
3
votes
2answers
163 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 ...
3
votes
0answers
131 views

Simplifying Relations in a Group

Let $K$ be the group generated by four elements $x_1,\cdots,x_4$ with relations that any simple commutator with repeated generator is trivial; for example, $[[x_2,[x_1,x_3]],x_3]=1$. As I have asked ...
3
votes
1answer
633 views

Unpacking the Diagonal Lemma

I am studying from Boolos' Computability & Logic (3rd edition). I need help unpacking what the Diagonal Lemma states, and understanding its proof. The Diagonal lemma is formalized on page 105 from ...
3
votes
2answers
131 views

Upper and Lower bounds on proof length

Given a First Order language say, for arithmetic $\langle 0, 1, +,\cdot ,^\wedge, S \rangle$, Can one establish any lower or upper bounds on the length of proofs from certain recursively enumerable ...
2
votes
1answer
109 views

A Turing machine for which halting is outside ZFC

If, given Turing machine T, "T halts" or "T doesn't halt" could be derived from axioms of ZFC, halting problem would be in R. As it isn't, there must exist a Turing machine for which truth or ...
2
votes
1answer
406 views

Is this undecidable language recognizable?

Is this language: $L = \{\langle M\rangle : \text{$M$ is a Turing machine and $L(M)$ is decidable}\}$ which I know that is undecidable, turing-recognizable? Is its complement recognizable? ...
0
votes
0answers
46 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 ...
0
votes
2answers
92 views

Can all programs be modeled as operations of elementary arithmetic operations on inputs?

In mathematics and computabiltiy theory, we treat all inputs and intermediate results and final outputs as natural number. While algorithms/programs themselves are considered natural numbers, here we ...
7
votes
2answers
328 views

Is there any generalization of the hyperarithmetical hierarchy using the analytical hierarchy to formulas belonging to third-order logic and above?

As I understand, hyperarithmetical sets are defined according to the analytical hierarchy, that is, second-order-logic formulas. There is a generalization of hyperarithmetic theory named α-recursion ...
5
votes
4answers
1k views

The word problem for finite groups

The word problem for finite groups is decidable. Is it obvious that this is true? In particular, I'm not entirely sure about what it means for the problem to be decidable (in this case---I think I ...
4
votes
2answers
79 views

Uncomputability of subset relation

I suppose this obvious question should already be answered in plenty of places, but for some reasons I cannot find a proof of this anywhere. Prove or disprove that their exist a set $X$ that is ...
4
votes
2answers
92 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}$ ...
4
votes
0answers
73 views

Is the measure induced by the Mandelbrot set computable on rational rectangles?

Is there a computable function that, given a positive rational number $\epsilon$ and a rectangle with rational corners $A$ returns a number $f(A,\epsilon)$ such that $|\mu(A \cap ...
4
votes
1answer
79 views

Is every context free language equivalent to one whose grammar has only one non-terminal symbol?

A context free language is generated by a context free grammar, which can be expressed in the Backus-Naur form e.g. I believe that if we only allow one nonterminal symbol in the grammar, the resulting ...
4
votes
2answers
468 views

An “uncountable” Turing Machine?

A proof of the insolubility of the halting problem is a diagonalization, which I'm sure most of you have seen. I am not very familiar with set theory, but it strikes me as similar to Cantor's proof of ...
3
votes
1answer
72 views

Proof that $\{ e \ | \ \forall p$ prime$: \varphi_e (p) \downarrow \}$ is not $\Delta_2$

This is a problem I've come across in my exam studies, and neither me nor my friend in the same course have been able to solve, so it would be good to see how it's done before the exam in a couple of ...
3
votes
1answer
72 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 ...