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).
Questions tagged [computability]
2295 questions
164
votes
1 answer
What properties of busy beaver numbers are computable?
The busy beaver function $\text{BB}(n)$ describes the maximum number of steps that an $n$-state Turing machine can execute before it halts (assuming it halts at all). It is not a computable function because computing it allows you to solve the…
Qiaochu Yuan
- 399,051
- 46
- 864
- 1,261
76
votes
6 answers
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, that there are some simple periodic formulas to…
Dims
- 1,069
- 1
- 10
- 17
63
votes
3 answers
Recognizable vs Decidable
What is difference between "recognizable" and "decidable" in context of Turing machines?
metdos
- 917
- 2
- 8
- 10
43
votes
5 answers
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 computer science. Why? Do we have any more…
GMB
- 4,118
- 1
- 19
- 34
41
votes
6 answers
In what sense does a number "exist" if it is proven to be uncomputable?
Uncomputable functions: Intro
The last month I have been going down the rabbit hole of googology (mathematical study of large numbers) in my free time. I am still trying to wrap my head around the seeming paradox of the existence of natural numbers…
Andreas
- 2,299
- 3
- 12
39
votes
6 answers
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" (describe) it, can't we?
islamfaisal
- 598
- 4
- 13
36
votes
3 answers
Can someone explain the Y Combinator?
The Y combinator is a concept in functional programming, borrowed from the lambda calculus. It is a fixed-point combinator. A fixed point combinator $G$ is a higher-order function (a functional, in mathematical language) that, given a function $f$,…
Chris Taylor
- 28,215
- 6
- 83
- 123
32
votes
1 answer
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 Aaronson have expressed the opinion that the…
user21820
- 55,389
- 9
- 92
- 243
29
votes
5 answers
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 the answer is no, because $\mathbb{R}$ is not a…
Ricky Bobby
- 713
- 8
- 15
29
votes
6 answers
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 find a single program that allows that. It is strange…
Artium
- 940
- 1
- 9
- 18
28
votes
1 answer
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 mathematicians reading this paper suffer from the…
Stephen
- 14,064
- 1
- 36
- 49
27
votes
2 answers
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 numbers."
I remember my professor saying incomputable…
joker
- 429
- 6
- 10
25
votes
13 answers
What is the fastest growing total computable function you can describe in a few lines?
What is the fastest growing total computable function you can describe in a few lines?
Well, not necessarily the fastest - I just would like to know how far an ingenious mathematician can go using only a few lines, and what systematic approaches…
Nik Z.
- 1,821
- 17
- 28
23
votes
4 answers
Is chess Turing-complete?
Is there a set of rules that translates any program into a configuration of finite pieces on an infinite board, such that if black and white plays only legal moves, the game ends in finite time iff the program halts?
The rules are the same as…
coffeemachine
- 271
- 3
- 5
22
votes
3 answers
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 try to do basic arithmetics with roman numbers,…
Bruno Alessi
- 431
- 3
- 5