10
votes
Does the physical Church-Turing thesis imply that all physical constants are computable?
You appear to be positing a universe where (a) the fine-structure constant has an exact value and (b) we can measure as many digits of it as we want. Thus, if a Turing machine cannot compute the exact ...
- 24.9k
8
votes
Accepted
Does the physical Church-Turing thesis imply that all physical constants are computable?
Yes, if you somehow had a scheme that allows to compute/measure more and more digits of the fine-structure constant $\alpha$ then $\alpha$ should be Turing computable according to the Church-Turing ...
- 4,485
8
votes
Accepted
Is Biological Computation a theme covered by the Theoretical Computer Science?
Yes there is some overlap, for instance the conference Unconventional Computation and Natural Computation (UCNC) covers theoretical computer science topics related to biological computation.
From the ...
- 4,485
7
votes
Accepted
Why do people bring real-life Quantum Computing to the discussion of the Church-Turing thesis?
I've written the following to talk about the connections between quantum computation and the (extended) Church-Turing thesis. Your question appears to have several other questions, which I don't ...
- 978
5
votes
Accepted
Equivalence of a physical computer and Turing machine
You certainly are right that if someone says "a physical computer is just a Turing machine" then they are telling a bit of a stretcher. More accurate would be something like "anything ...
- 213
5
votes
Accepted
How exactly is solving the random circuit sampling problem a computation in the Church-Turing thesis sense?
Answer from the other SE site
The Church-Turing thesis is not in and of itself a rigorous concept, but rather a judgment on rigorous concepts of computability. As such, it's negotiable. The language ...
- 461
5
votes
Why do people bring real-life Quantum Computing to the discussion of the Church-Turing thesis?
I'll address just the first part of your question.
Neither the Church–Turing Thesis nor the Extended Church–Turing Thesis is a purely mathematical or formal statement. You phrased the C–T Thesis as, &...
- 7,590
2
votes
Is this a good definition of computability?
First of all, the place for this question is cs.se, not here. But since I've already written an answer, I'll leave it.
There is a formal definition of computability: a function $f$ is computable if ...
- 5,616
2
votes
Is true randomness and the physical Church-Turing thesis incompatible?
The Church-Turing thesis is about (partial) functions $\mathbb{N} \to \mathbb{N}$ (or $\Sigma^* \to \Sigma^*$ for a finite alphabet $\Sigma$). How do you define a definite value based on some random ...
- 3,083
1
vote
Why do people bring real-life Quantum Computing to the discussion of the Church-Turing thesis?
The Church-Turing thesis is a kind of axiom that links an informal notion of "computation by pen and paper method" to a formal definition of a turing machine model. It has been proven that ...
1
vote
Is true randomness and the physical Church-Turing thesis incompatible?
In a way, if we imagine time continuing indefinitely then with probability 1, random numbers, obtained from I guess the collapse of the wave function in quantum mechanics, will form a non-computable ...
- 4,485
1
vote
Is Biological Computation a theme covered by the Theoretical Computer Science?
Grzegorz Rozenberg worked a lot on the way in which ciliates assemble their genes. Besides the theoretical models derived from these operations, I believe he thinks that this assembly is a ...
- 462
Only top scored, non community-wiki answers of a minimum length are eligible