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)
54
questions
2
votes
1answer
41 views
Can current quantum computers decide languages that Turing Machines cannot?
I am currently learning Computing Theory at university, and we were on the topic of Turing-Decidability, Recognizability, etc. Showing that a problem is undecidable with Turing machines due to ...
0
votes
0answers
52 views
Who initiated the term “Extended Church-Turing Thesis”? or What papers that initiated this term?
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
42 views
Universal Turing Machine run on Universal Turing Machine
I am curious, what happens if we run Universal Turing Machine on itself?
1
vote
2answers
89 views
Turing machine where the next step is determined by the state and the symbols up to the read/write head
Given a modified type of turning machine where
$\delta = Q\times \Gamma^* \implies Q\times \Gamma \times \{L,R\}$
where the next step of the machine is determined by the current state and whatever ...
0
votes
2answers
43 views
Are Linear Bounded Automatons Turing Complete?
Linear Bounded Automatons are just Turing Machines with finite tape, instead of infinite tape.
But this causes them to not be Turing Complete? Why?
2
votes
1answer
97 views
How to come up with a language that is recognizable but not co-recognizable?
Forming a language that is recognizable but not co-recognizable. I'm having trouble coming up with a language with these properties. A recognizable language is a language $A \subseteq \Sigma^*$ iff $A ...
8
votes
2answers
1k views
Does this article imply that Turing-Computability is not the same as “effectively computable”?
First of all, I apologize if this has been asked, but I truly didn't find anything.
I've stumbled across this article. It says that there is a problem that only Quantum Computers can solve.
In my ...
1
vote
1answer
33 views
Is turing completeness related to recursive enumerable languages?
I recently came across this term "Turing complete" in my study of morphogenesis models. When I looked up, it said that a turing complete machine can simulate a universal turing machine.
When I ...
1
vote
1answer
74 views
Empirical evidence for the Church-Turing thesis in other disciplines
I am aware of the fact that, since the concept of "effectively calculable function" is not rigorous or formally definable, the Church-Turing thesis may not be proven by symbolic or formal reasoning ...
1
vote
2answers
67 views
Would any continuous model of the universe have/be based on hypercomputational laws?
I've read that when Turing-Church thesis is applied to the universe and physics, one of the three interpretations that we can use and is defended by some important physicists is that:
"The universe ...
0
votes
0answers
63 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
1answer
44 views
The Church-Turing Thesis (Hello World tester) contradiction and randomized algorithms
The Church-Turing thesis proves that there is no algorithm (or program) $H$ that says whether a program $P$ written in a language, say $C$, on an input $I$ outputs the sentence ...
0
votes
3answers
189 views
Is a Turing machine too strong of a model to model physical computation?
I've heard many times people debate the possibility of a real world computation that is impossible for a Turing machine, especially in the context of a human mind. Implying that the Church-Turing ...
0
votes
1answer
55 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'$...
23
votes
2answers
6k views
Do any programming languages use general recursive functions as their basis?
This is a naïve and, therefore, possibly malformed question, so apologies in advance!
My view is that a Turing Machine can be seen as the computational basis for procedural/imperative programming ...
0
votes
1answer
36 views
Comparing turing based programming languages
According to Turing thesis, Can we say all programming languages that support turing machine like C have same power for solving problems and performing algorithms? In other words is there any ...
5
votes
0answers
50 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,...
1
vote
0answers
29 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 ...
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 ...
1
vote
2answers
247 views
prove A is co-re
Working on some cs theory and solving a problem on computationally [=recursively] enumerable languages:
A language $A\subseteq \{0,1\}^*$ is co-c.e. if and only if there is a decidable language
...
1
vote
1answer
106 views
It is possible to write any program (i.e. Turing complete) with just one single expression?
So I'm currently taking discrete math II at my university and I came across a somewhat philosophical question (so I apologize if this is question is hard to answer precisely) of whether mathematicians ...
29
votes
2answers
4k views
Church-Turing Thesis and computational power of neural networks
The Church-Turing thesis states that everything that can physically be computed, can be computed on a Turing Machine.
The paper
"Analog computation via neural networks" (Siegelmannn and Sontag, ...
3
votes
1answer
277 views
The Church-Turing-Thesis in proofs
Currently I'm trying to understand a proof of the statement:
"A language is semi-decidable if and only if some enumerator enumerates it."
that we did in my lecture. One direction of the proof goes ...
2
votes
1answer
137 views
weak Church-Turing thesis
(weak) Church-Turing thesis states every physically realizable computation device can be simulated by a Turing machine (not necessarily efficiently).
(1) Then Does any model that is not physically ...
6
votes
3answers
197 views
Does computability according to Church-Turing thesis include side effects?
To my understanding:
The Church-Turing thesis means that one could theoretically compute anything that can be computed using either a Turing Machine or the Lambda Calculus.
The Lambda Calculus is ...
0
votes
2answers
56 views
Is a physical process with unbounded input Turing equivalent?
Church-Turing thesis states that any effectively computable process is computable by a TM. Let's assume for now that it means that every physical machine is computable by a TM. Let's call it A.
Now ...
12
votes
3answers
2k views
Can every self-modifying algorithm be modelled by a non-selfmodifying algorithm?
If we have any arbitrary computer program that can modify its instructions, is it possible to simulate that program with a program that cannot modify its instructions?
Edit:
I am new to ...
1
vote
0answers
52 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 ...
8
votes
1answer
153 views
Church-Turing and physical PDEs
When I read about the Church-Turing thesis it seems to be a common claim that "physical reality is Turing-computable." What is the basis for this claim? Are there any theoretical results along these ...
3
votes
1answer
124 views
Whatever that can be done using algorithm can be done using Turing machine
In 1937 how was Alan Turing so sure that all that can be done using algorithms can be implemented using a Turing machine?
Since that period many new algorithms were implemented. What was his ...
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 ...
5
votes
3answers
886 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 ...
2
votes
4answers
210 views
Problems understanding proof of smn theorem using Church-Turing thesis
I am reading Barry Cooper's Computability Theory and he states the following as the s-m-n theorem:
Let $f:\mathbb{N}^2\mapsto\mathbb{N}$ be a (partial) recursive function. Then there exists a ...
17
votes
3answers
7k 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?
5
votes
0answers
196 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 ...
4
votes
3answers
465 views
Can every program be parallelized infinitely and automatically?
In my previous question ( Can Turing machines be converted into equivalent Lambda Calculus expressions with a systematic approach? ), I got the answer that it is indeed possible.
And as I have read ...
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 ...
2
votes
3answers
244 views
Church-Turing thesis is a dualism
Church-Turing thesis : Every effectively calculable function is a TM-computable function.
But, hypercomputation models are strictly more powerful than TM and can solve TM-uncomputable problems on the ...
1
vote
1answer
434 views
Why Turing wasn't wrong? [closed]
Computer science is a science and as a science each thesis can be refutable. So, why there is no "major" counter-thesis?
After all, Einstein was a well known "genius" and has lived a long life and he ...
1
vote
2answers
574 views
Curry Howard correspondence and Church-Turing thesis
Curry-Howard correspondence states the equivalence between logic/deduction and types/programs.
The Church-Turing thesis states the equivalence of some models of computation. Specifically, all ...
2
votes
1answer
1k 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 ...
8
votes
1answer
558 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 ...
6
votes
2answers
3k views
Why is Oracle Turing Machine important?
As you know, an Oracle Turing Machine (OTM) is a "black box" which somehow can tell us whether a given Turing machine with a given input eventually halts. By Church's Thesis it is impossible to design ...
1
vote
2answers
659 views
Examples of processes / problems that cannot be tackled by Turing Machines
I know that there are problems that cannot be solved by any algorithm, such as the Halting problem.
I also know that some processes cannot be even adequately approximated by any Turing Machine (...
9
votes
2answers
724 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 ...
1
vote
1answer
130 views
Are conditionals necessary in computation? [duplicate]
I know this question might seem weird, maybe I'm just overthinking, but this is really troubling me because I've been a computer engineer for some time now and conditionals (if statements for instance)...
3
votes
3answers
725 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 ...
10
votes
2answers
3k views
Clear, complete, proof that a language is Turing Compete?
I have seen web sites that purport to "prove" that HTML5+CSS is Turing Complete.
I have seen web sites that purport to "prove" that SQL is Turing Complete.
I have seen a bunch of web sites that ...
7
votes
2answers
386 views
To what does typing correspond in a Turing Machine?
I hope my question makes sense: Starting with the premise that the untyped $\lambda $ calculus is equivalent in power to a Turing machine, to what in a Turing machine does adding types to the $\lambda ...
3
votes
2answers
574 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 ...
