Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [computability]

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).

17
votes
1answer
890 views

Computability viewpoint of Godel/Rosser's incompleteness theorem

How would the Godel/Rosser incompleteness theorems look like from a computability viewpoint? Often people present the incompleteness theorems as concerning arithmetic, but some people such as Scott ...
45
votes
3answers
22k 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, ...
11
votes
1answer
722 views

Approximate spectral decomposition

I am interested in effective and computations for finding approximate spectral decompositions in some suitable format. Namely, let $A: H \rightarrow H$ be a Hermitian operator on an $n-$dimensional ...
26
votes
5answers
5k 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 ...
2
votes
2answers
171 views

Computable extension to $Σ_1$-sound system that is $Σ_2$-unsound?

Recently, I wrote this post showing (if I did not make a mistake) essentially that: For any nice formal system $S$ that is $Σ_1$-sound there exists some extension $S'$ that is $Σ_1$-sound but $Σ_2$-...
24
votes
6answers
4k 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 ...
9
votes
1answer
488 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 $t-...
5
votes
1answer
144 views

Pairing in Presburger arithmetic

Is it possible to define pairing function (and the inverses) in Presburger arithmetic? I would guess no but I can't locate a reference nor construct a proof to one way or another.
30
votes
7answers
4k views

Example of uncomputable but definable number

Every computable number is definable. However, the converse is not true. What is an example of a real number that is definable but that is NOT computable? I guess if it is there, we can "define" (...
9
votes
3answers
3k 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 ...
8
votes
4answers
2k views

explicit upper bound of TREE(3)

TREE(3) is the famously absurdly large number that is the length of a longest list of rooted, 3-colored trees whose $i$th element has at most $i$ vertices, and for which no tree's vertices can be ...
5
votes
1answer
548 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 ...
0
votes
1answer
65 views

Finding languages such that $L_{1} \subseteq L_{2} \subseteq L_{3}$ where $L_{1}, L_{3} \notin \mathbb{R}$, $L_{2} \in \mathbb{R}$

I am struggling to find such languages $L_{1}$, $L_{2}$, and $L_{3}$ such that $$ L_{1} \subseteq L_{2} \subseteq L_{3} $$ where $L_{1}, L_{3} \notin \mathbb{R}$ and $L_{2} \in \mathbb{R}$. I know ...
36
votes
3answers
65k views

Recognizable vs Decidable

What is difference between "recognizable" and "decidable" in context of Turing machines?
19
votes
5answers
1k 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 ...
6
votes
4answers
1k views

A mathematically mature introduction to Turing Machines and Computability [reference-request]

In the computer science course for mathematicians held at my university Turing Machines have been presented very briefly. So much so that I didn't quite get why they are relevant to mathematics. I did ...
16
votes
1answer
537 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?
7
votes
4answers
7k 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} \...
5
votes
1answer
332 views

How can know if a proof technique can actually prove something? Specifically, induction

Induction is an incredible tool to prove some propositions. Although it seems that these propositions require some level of simplicity for us to be able prove them using only induction. If we wanted, ...
1
vote
2answers
443 views

Is there a version of turing-completeness for total programming languages?

Languages like Agda, and Charity are not turing complete. However, they are still useful languages because they are able to simulate any provably terminating Turing machine. Is there a term for this ...
6
votes
1answer
502 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 ...
4
votes
1answer
174 views

Markov's paper on insolubility of the homeorphy problem

I am looking for an English translation of Markov's 1958 paper, On insolubility of the homeorphy problem, which I remember coming across on a website for a computational topology course (taught by ...
4
votes
1answer
288 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 $t-...
3
votes
3answers
1k 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
300 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
293 views

Does a $\Pi_2^0$ sentence becomes equivalent to a $\Pi_1^0$ sentence after it has been proven?

I heard that the P vs NP question is equivalent to a $\Pi_2^0$ sentence, and that the Riemann hypothesis is equivalent to a $\Pi_1^0$ sentence. Many known mathematical theorems state that some ...
0
votes
1answer
338 views

How many Turing degrees are there?

So I know there are precisely $2^{\aleph_0} $ Turing degrees, but is there a proof of this somewhere?
4
votes
1answer
53 views

First-order formula in first-order language, another open language where equivalence true on the naturals?

For any first-order formula $X$ in the first-order language $\langle 0, S, \le\rangle$ (possibly with free variables) does there necessarily exist another open formula $Y$ such that the equivalence $X ...
3
votes
1answer
176 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 = \...
3
votes
1answer
65 views

Can we describe any subsets of $\mathbb{N}$ occurring in a late layer of the Constructible Universe?

There is a certain large countable ordinal referred to in the literature as $\beta_0$. It was first discovered by Paul Cohen, and here are some equivalent characterizations of it: The smallest ...
3
votes
1answer
685 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 1:...
3
votes
1answer
166 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 ...
2
votes
2answers
212 views

Why is there a $p\in \mathbb{N}$ such that $mr - p < \frac{1}{10}$?

I am reading the following part of the paper of Denef : Let $R$ be a commutative ring with unity and let $D(x_1,\dots , x_n)$ be a relation in $R$. We say that $D (x_1,\dots , x_n)$ is diophantine ...
1
vote
1answer
229 views

Example of a recursive set $S$ and a total recursive function $f$ such that $f(S)$ is not recursive?

Browsing wikipedia, I stumbled on the following: "The image of a computable set under a total computable bijection is computable." Given the form of the theorem, there must be some example of a ...
0
votes
1answer
36 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$, ...
0
votes
1answer
66 views

Finding the maximum $lcm$ of a set of numbers with sum $n$

Consider all possible values for $(a_1,\ldots,a_n)$ (where each $a_i$ may be a positive integer or 0) when $a_1 + \cdots + a_n = n$. Consider $(a_j,\ldots,a_k)$ the values in $(a_1,\ldots,a_n)$ ...
37
votes
5answers
3k 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 ...
15
votes
6answers
3k 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 ...
19
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 ...
21
votes
1answer
2k views

How to interpret “computable real numbers are not countable, and are complete”?

On page 12 of this (controversial) polemic http://web.maths.unsw.edu.au/~norman/papers/SetTheory.pdf Wildberger claims that Even the "computable real numbers" are quite misunderstood. Most ...
15
votes
3answers
1k views

Why does the fixed point theorem justify the existence of the factorial function?

I was learning about fixed point theorem in the context of programming language semantics. In the notes they have the following excerpt: Many recursive definitions in mathematics and computer ...
12
votes
1answer
2k views

Recognizing and Using Chaitin's Constant

As far as I understand, Chaitin's constant is the probability that a given universal Turing machine will halt on a random program. I understand that Chaitin's constant is not computable--if it were, ...
15
votes
2answers
858 views

Gödel's completeness theorem and the undecidability of first-order logic

I'm working through this module, "Undecidability of First-Order Logic" and would love to talk about the two exercises given immediately after the statement of Godel's completeness theorem. First, ...
5
votes
2answers
126 views

Can we implement $\omega^{CK}_1$ using $\omega^{CK}_1+1$ as an oracle?

Let $\omega^{CK}_1$ denote the least non-recursive ordinal. Suppose we have an unknown well-ordering of $\mathbb{N}$ of the order type $\omega^{CK}_1+1$ as an oracle. Is it possible to write an ...
11
votes
0answers
318 views

Does Chaitin's constant have infinitely many prime prefixes?

Define $f(n) = \lfloor 2^n \cdot \Omega \rfloor$, that is, $f(n)$ is the first $n$ bits of Chaitin's constant interpreted as a number written in binary. I am trying to figure out if $f(n)$ can have ...
9
votes
1answer
542 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$?
9
votes
1answer
920 views

Proving that $\Omega = (\lambda x.xx)(\lambda x.xx)$ is not typable in the simply typed lambda calculus

I am trying to prove that $\Omega = (\lambda x.xx)(\lambda x.xx)$ is not typable in the simply typed lambda calculus. Surprisingly, different textbooks and lecture notes do not contain that proof, ...
7
votes
1answer
177 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
220 views

Eager vs. lazy interpretation of recursive functions

One of the ways of defining the set of recursive functions is to define first a language $L$ by induction in the following way: $\mathsf{Z}^1 \in L$; $\mathsf{S}^1 \in L$; $\mathsf{P}^n_k \in L$ for ...
3
votes
1answer
932 views

Prove a set is not recursive / recursively enumerable

I have two sets B which is recursively enumerable and is not recursive, and A which is recursive. Is $A-B$ recursive and / or recursively enumerable? What about $B-A$? $B-A$ is obviously recursively ...