What is Computable: Definition and 20 Discussions

Computability is the ability to solve a problem in an effective manner. It is a key topic of the field of computability theory within mathematical logic and the theory of computation within computer science. The computability of a problem is closely linked to the existence of an algorithm to solve the problem.
The most widely studied models of computability are the Turing-computable and μ-recursive functions, and the lambda calculus, all of which have computationally equivalent power. Other forms of computability are studied as well: computability notions weaker than Turing machines are studied in automata theory, while computability notions stronger than Turing machines are studied in the field of hypercomputation.

View More On Wikipedia.org
Recent contents Top users
  1. fresh_42

    Explore Alan Turing's Computable Numbers & Generate Pi with Python

    I found this article about Alan Turing and his concept of Turing machines on the AMS website. Since we often get questions about countability and computability I thought it is worth sharing. https://blogs.ams.org/featurecolumn/2021/12/01/alan-turing-computable-numbers/ It also contains a Python...
  2. nomadreid

    I Computable reals and r.e./Diophantine

    To not get caught up on side issues, I will assume that the Church Thesis is true, whether or not the assumption is necessary. That said: I start with the rough definitions: [1] A recursive set A is a set A for which there exists an algorithm that can tell in a finite time, for any given a...
  3. platosuniverse

    B Is spacetime a quantum error correcting code?

    This is a fascinating discussion. I know some people don't want to debate this or they can't debate it but the truth doesn't care about your feelings. This isn't speculative, it's backed by Scientific research. First paper. Is Spacetime an Error Correcting Code. Published in the Journal of High...
  4. B

    Prove that the given function is totally computable

    Hello, I'm trying to prove following problem. 1. Homework Statement Graph of function ƒ : ℕ→ℕ is set {(x, ƒ(x)), x ∈ ℕ and ƒ(x) ≠ ⊥} ⊆ ℕ2. Prove that function ƒ is totally computable when ƒ(x) is defined for every x ∈ ℕ and his graph is recursively enumerable set Homework Equations The...
  5. bhobba

    Non Computable Functions And Godel's Theorem

    Hi All I normally post on the QM forum but also have done quite a bit of programming and did study computer science at uni. I have been reading a book about Ramanujan and interestingly he was also good friends with Bertrand Russell. You normally associate Russell with philosophy but in fact...
  6. cobalt124

    I Proof that BB(k) grows faster than any computable function

    Hi, layman post, not sure what thread level I need. From post https://www.physicsforums.com/threads/the-busy-beaver-function.942741/, I've been working my way through https://www.scottaaronson.com/busybeaver.pdf and come to section "1.3 The Busy Beaver Function", which states: "The Busy Beaver...
  7. TheQuestionGuy14

    B What do people mean when they say the Universe is Computable

    Hey. I was just wondering what people mean when they say physics and the universe is computable, I always thought it meant that the universe is measurable/calculable, but someone said to me that it meant the universe works like a computer/simulation. So, what does it actually mean?
  8. nomadreid

    I Extension of Turing computable

    The short version: If you had an infinite amount of time, would the standard proof for the insolubility of the halting problem still work? The longer version: A simple proof that there are non-computable functions can be easily seen by the fact that there are only countable number of Turing...
  9. ErikZorkin

    I Eigenvalue degeneracy in real physical systems

    I understand this question is rather marginal, but still think I might get some help here. I previously asked a question regarding the so-called computable Universe hypothesis which, roughly speaking, states that a universe, such as ours, may be (JUST IN PRINCIPLE) simulated on a large enough...
  10. K

    Computability in Classical Physics

    I was reading the book "Emperor's New Mind" by Roger Penrose which deals with understanding the nature of mind in the sense that it is algorithmic or not. In one of the chapters he explains that the deterministic world of the Newtonian Theory can still be non-computable. He explains this as...
  11. B

    Symbol in Alan Turing's On Computable Numbers

    In Alan Turing's On Computable Numbers, he explains in his second paragraph the general notion of computable numbers. In doing so, he writes "In [symbol][symbol] 9, 10 I give some arguments...". I will include a screenshot of these symbols in this post. Do any of you know what these symbols...
  12. xortdsc

    De Broglie wavelength computable by just fixing speed of light ?

    Hi, I was wondering if it is possible to compute e.g. bohr radii for a metric system whose correspondence to real units is unknown and only the speed of light is known. Let's say the only thing I know is that lightwaves travel x spaceunits in t timeunits, therefore defining the speed of...
  13. D

    Computable Normal Numbers: Is There a Known Answer?

    Wikipedia is not very clear on this. Is there a known computable normal number? I found this paper: http://www.glyc.dc.uba.ar/santiago/papers/absnor.pdf But I'm not sure if it's been peer reviewed.
  14. R

    There are effectively computable numerical functions which aren’t prim

    This is from Peter Smith's Gödel without tears. I don't agree with this. If it appears in the list of p.r. functions then it is p.r. I don't see why he thinks that if x is in the list of p.r. functions then it is not p.r.
  15. marcus

    Feynmans of geometry: computable trans. amps. by K+Le+P algorithm

    Kisielowski Lewandowski Puchta have made a significant advance in calculating the transition amplitudes between quantum states of geometry. They have found a systematic algorithm that enumerates the (generalized) spinfoam-like histories by which one state evolves into another. And in this case...
  16. C

    Computable real numbers

    I was watching a lecture on computable real numbers, And in the lecture they talked about how this set of numbers is countable. And I could see this because the numbers that a computer generates would be listable, I could write them down on a list. For example pi is a computable real number...
  17. K

    Formalizing Real-Valued Computable Functions

    Hi there, I'm currently reading Li and Vitanyi's book on Kolmogorov complexity. Unfortunately, I don't have a good background in computability/recursive function theory. I have a question about their definition of a computable real-valued function. The authors first define recursive functions...
  18. S

    Argument that all computable universes are real

    argument that all computable universes are "real" I haven't been on this forum in a while, and I'm sure this kind of thing has been talked about many times, but I thought I'd bring it up again so I could discuss it with you guys. Here's my argument. Start with a human being named John. He...
  19. B

    Turing machine, computable function.

    From Nielsen-Chuang:how might we recognize that a process in nature computes a function not computable by a turing machine?
  20. D

    Incompleteness of Computable Numbers

    Can someone prove to me why computable numbers are not closed under the taking of suprema?
Back
Top