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)

8 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
5
votes
0answers
51 views

The evolution of the term “recursive” from Goedel to Church to present day

I'm currently studying some of the history of computation / computability, in the early days known as recursion theory. I see Goedel's definition of recursive functions seems significant in his paper,...
5
votes
0answers
203 views

Computational power of Actor Model

In the question below, let TM be Turing machine, NTM be nondeterministic Turing machine and PTM be probabilistic Turing machine. In his paper "Actor Model of Computation: Scalable Robust Information ...
1
vote
0answers
50 views

Universal Turing Machine run on Universal Turing Machine

I am curious, what happens if we run Universal Turing Machine on itself?
1
vote
0answers
30 views

The rules for Turing Machine ,equivalence?

We have regular expression for DFA and NFA, at the same time, we have CFG for PDAs, What do we have for Turing Machine? If this questions is too obvious, please points me some reading, I am just ...
1
vote
0answers
58 views

Canonical definition of suitable encoding

I've had several Computer Science courses and, from what I recall, I've never been given a rigorous definition of suitable encoding. Definitions always tend to use effective method or some synonym to ...
0
votes
0answers
88 views

Is “Extended Church-Turing Thesis” the same as “Cobham-Edmonds Thesis”?

I have been looking for any reference regarding the term: "Extended Church-Turing Thesis" [some people will call it, Strong Church–Turing Thesis]? Does anyone defined it or it is just people in ...
0
votes
0answers
75 views

Church-Turing thesis and hypercomputation?

The Church-Turing is a hypothesis about the nature of computable functions. It states that a function on the natural numbers is computable by a human being following an algorithm, ignoring resource ...
0
votes
0answers
126 views

Does Turing Completeness imply the existence of a Universal Program?

Please correct me if at any time my definitions are wrong. Suppose we have a programming language $L$ over some set $D$ with semantic (partial) n-ary functions $\varphi^n:D \to (D^n \to D)$. Assume $L ...