Computable Definition and 20 Threads

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

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

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

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

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

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

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?

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

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

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

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

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

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.

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.

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

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

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

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

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

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