Questions tagged [church-turing-thesis]
For questions about the interpretation, extension and validity of the Church-Turing thesis, the hypothesis that states that a function is effectively calculable by a human if and only if the function is computable (on a Turing machine)
10
questions
17
votes
3answers
9k views
Is there any uncountable Turing decidable language?
There are many(and I mean many) countable languages which are Turing-decidable. Can any uncountable language be Turing decidable?
8
votes
1answer
675 views
Does Church-Turing thesis also apply to artificial intelligence?
By Church-Turing's thesis, it is impossible to design an algorithm to decide the halting problem.
Does the word algorithm in this context include artificial
intelligence or not, that is, does ...
15
votes
5answers
4k views
Turing machine + time dilation = solve the halting problem?
There are relativistic spacetimes (e.g. M-H spacetimes; see Hogarth 1994) where a worldline of infinite duration can be contained in the past of a finite observer. This means that a normal observer ...
10
votes
2answers
839 views
Analog computers and the Church-Turing thesis
I'd like to quote from Nielsen & Chuang, Quantum Computation and Quantum Information, 10th anniversary edition, page 5 (emphasis mine):
One class of challenges to the strong Church–Turing ...
3
votes
3answers
755 views
Rice's theorem vs Turing completeness
I would like to clarify this because I see some kind of contradiction between Rice's theorem and Turing completeness.
This is the problem:
In building an Universal Turing Machine to emulate another ...
2
votes
1answer
2k views
Is a partial function Turing-computable?
From my understanding for a function to be considered Turing-computable the Turing machine which computes it must terminate for all inputs (according to this http://planetmath.org/turingcomputable and ...
6
votes
3answers
2k views
Is there an algorithm for converting Turing machines into equivalent Lambda expressions?
We know that Turing machines and Lambda Calculus are equivalent in power. And There are proofs for that, I'm sure.
But is there an algorithm, a systematic way for us to convert a Turing machine into ...
6
votes
3answers
950 views
Would creating a complete computer simulation of the human brain prove the Church-Turing thesis?
According to Wikipedia, the Church-Turing thesis "states that a function on the natural numbers is computable by a human being ignoring resource limitations if and only if it is computable by a Turing ...
4
votes
2answers
600 views
Can the Lambda Calculus or Turing Machines model signals, callbacks, sleep/wait, or buses?
I have a deep appreciation for formalisms like the Turing Machine and the $\lambda$-Calculus, and enjoy studying them and learning more about how they relate to physical computers. I am now learning ...
0
votes
1answer
66 views
Isn't the given characterisation of recursively enumerable subsets of the class of all recursively enumerable languages?
$S$ is a subset of the class of all recursively enumerable languages over some finite symbols then $S$ is recursively enumerable iff
If $L$ is in $S$ and $L'$ is a language such that $L ⊆ L'$ and $L'$...
