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)

Filter by
Sorted by
Tagged with
1 vote
1 answer
55 views

Turing Machine, UNLIMITED number of steps left or right on the tape?

In the Church-Turing thesis Wiki page, there are a set of descriptions of the "behavior of a computor—`a human computing agent who proceeds mechanically'". I am content with all of them, ...
  • 604
1 vote
1 answer
65 views

Why is the Church-Turing thesis not accepted as fact?

I recognize that it has overwhelming consensus at this point, but from what I understand, it's still technically considered "probably true" instead of "definitely true". If we go ...
  • 284
1 vote
1 answer
66 views

Generalization of computability to continuous for loops?

A computable function, formulated in the sense of mu recursion, can compute a for or do loop over some (possibly infinite) integer range. I was wondering if a suitable generalization exists that ...
1 vote
1 answer
97 views

What is the difference between the Church-Turing thesis and the Church-Turing-Deutsch principle?

I am trying to get a better handle on the Church-Turing thesis, and I am confused by the difference between the two ideas in the title. The wikipedia page for the Church-Turing thesis says, the ...
-1 votes
2 answers
51 views

Are there infinitely many distinct implementations of any algorithm using any Turing-complete computational model?

Subject pretty much says it all. My strong impression is that for any algorithm and any choice of programming language or computational model, if it's Turing-complete, then there must be infinitely ...
  • 284
2 votes
1 answer
63 views

Does Nondeterministic TM is a counterexample of Extended Church-Turing Thesis?

We know that Extended Church-Turing Thesis (or Cobham's thesis) states that any 'reasonable' model of computation can be equivalent to Turing Machine model in at most polynomial time overhead. People ...
  • 729
2 votes
2 answers
143 views

How do we define the term "computation" across models of computation?

How do we define the term computation / computable function generically across models of computation? Beginning with the textbook definitions of: {Linz, Sipser and Kozen} for "computable function&...
  • 91
0 votes
1 answer
18 views

Question regarding notation of a language decidability

$1.\: A_{DFA} = \{\langle B, w \rangle \mid B \text{ is a } DFA \text{ that accepts input string } w \}$ $2.\:A_{DFA} = \{\langle B \rangle \mid B \text{ is a } DFA \text{ that accepts input string } ...
  • 11
1 vote
1 answer
142 views

Church-Turing Thesis - the mechanical model - the turing machine- its limits and its equivalence with a modern digital computer

Well in many texts and places I have seen a called statement, which claims it self to the famous "Church Turing Thesis". I have seen many texts say that based on Church-Turing Thesis : &...
1 vote
1 answer
140 views

Computability of function composition

I have some problems to understand computability and hope you can help me. In the lecture we had following problem: Consider the three partial functions $f,g,h\colon N \to N$, where $f$ is computable ...
  • 23
1 vote
2 answers
92 views

The Church-Turing thesis and Hyper-computation

I am not a computer scientist and this is my first question. This question is a question in layman terms and I also want the answer in layman terms. When I searched hyper-computation. There was a list ...
4 votes
1 answer
179 views

Kleene's Theorem and TMs

I wanted to know that based on Kleene's theorem (a language is regular iff some FSA recognizes it), does every regex have a TM (Turing machine) that halts on exactly the same language? Is this ...
  • 65
1 vote
1 answer
176 views

Are there more Turing-unrecognizable languages than recognizable?

Say you generated a language by looking at the output of a lexicographic enumerator and flipping a coin for each string, adding it to the language on heads. What would be the chance of this language ...
0 votes
1 answer
263 views

Halting problem for turing machines with one input

My question is: Is there a simple construction similar to Turing's 'liar' program that shows that Turing machines plus a halting oracle cannot decide if a given Turing machine halts on all inputs. ...
  • 163
-1 votes
1 answer
191 views

Computational power of a Turing Machine with infinite states

Consider a turing machine with infinite states. This machine is identical to a regular machine. Only that number of states could be infinite. Does this machine has more computational power than a ...
-1 votes
1 answer
53 views

running RAM on a given input

I understand how RAM commands work but I am unable to understand how we use a given input string and find the output. For instance, there's a Random Access Machine which has an input {0,1}*. The ...
  • 167
0 votes
1 answer
139 views

change turing machine to RAM

How can we convert a given Turing Machine into a Random Access Machine? I understand that we can use the transition function to come up with a sort of algorithm but how can we translate all of it into ...
  • 167
1 vote
1 answer
296 views

How to prove the language of all Turing Machines that accept an undecidable language is undecidable?

I want to prove that $L=\{\langle M \rangle |L(M)\text{ is undecidable}\}$ is undecidable I am not sure about this. This is my try : Suppose L is decidable. Let $E$ be the decider from $L$. Let $A$ be ...
  • 147
3 votes
2 answers
152 views

Intuition for Church-Turing thesis for Turing machines

I can very clearly see "why" mu-recursion is a universal model of computation, i.e. why the Church-Turing thesis -- that any physically computable algorithm can be executed with mu-recursion ...
0 votes
1 answer
86 views

Is the languague L={<M>, M accepts a finite amount of words} decdidable?

Is $L=\{<M> | L(M) \ is \ finite\} $ decidable ? M is a TM. I think its relative simple to proof with the theorem of rice. But I am interested in a solution which does not use the Rice theorem. ...
  • 147
0 votes
2 answers
32 views

Equivalence between a TM and a changing TM

Let a changing TM be a TM which is not able to write the same symbol which is being read. Formal: $M^*=(Q,\Sigma,\Gamma,\delta,q_{accept},q_{reject})$,$\delta(q,a)=(q^*,a^*,c),a \neq a^*$ with $q,q^...
  • 147
0 votes
1 answer
45 views

About computable sets

Let TOT be the set of all Turing Machines that halt on all inputs. Find a computable set B of ordered triples such that: TOT = {e : ($\forall$x)($\exists$y)[(e, x, y) $\in$ B] This definition means ...
user avatar
2 votes
4 answers
799 views

To what extent is an x86 machine equivalent to a Turing Machine?

To what extent is the abstract model of computation specified by the x86 language Turing complete? The above question is related to this question: Is C actually Turing-complete? In theoretical ...
  • 91
0 votes
2 answers
94 views

There are functions with f (n) = f (2n) which can't be calculated

I have to proofe that there are functions defined by $f:\mathbb{N} \rightarrow \mathbb{N}, f(n)=f(2n), \forall n\in \mathbb{N}$, which are not-computable. However I'm not really sure about the correct ...
  • 1
-1 votes
2 answers
106 views

Why is nondeterminism physically not realizable?

Why it is so hard to make a nondeterministic computer? If such a device is physically realizable then would that be a counterexample to the extended Church-Turing thesis?
  • 109
0 votes
1 answer
105 views

Are Turing unrecognizable and undecidable languages, recognized and decided by hyper computation?

Do the hyper computing machines/models that are supposed to be more powerful than Turing machines, capable of recognizing and deciding the languages that are not recognizable/decidable by Turing ...
  • 611
0 votes
1 answer
142 views

Some questions about the Computability of Turing Machines

I'm learning for a test and I have some important questions about Computability of deterministic and non deterministic Turing Machines. Consider we have the partial functions $f,g,h,t: \mathbb{N} \...
4 votes
1 answer
222 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 ...
  • 519
1 vote
0 answers
71 views

Universal Turing Machine run on Universal Turing Machine

I am curious, what happens if we run Universal Turing Machine on itself?
1 vote
2 answers
161 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 ...
user avatar
0 votes
2 answers
253 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?
  • 215
2 votes
1 answer
783 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 ...
  • 35
8 votes
2 answers
1k views

Does this article imply that Turing-Computability is not the same as "effectively computable"?

I've stumbled across this article. It says that there is a problem that only Quantum Computers can solve. In my understanding, this should mean, intuitively, that this problem is "effectively ...
  • 394
1 vote
1 answer
352 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
1 answer
88 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 ...
  • 394
1 vote
2 answers
136 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 ...
  • 41
0 votes
0 answers
146 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 ...
  • 41
0 votes
1 answer
233 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 ...
  • 1,477
2 votes
3 answers
335 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
1 answer
82 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'$...
  • 151
24 votes
2 answers
7k 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
1 answer
37 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
0 answers
54 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
0 answers
31 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 ...
  • 123
18 votes
5 answers
5k 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 ...
  • 283
1 vote
2 answers
826 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
1 answer
115 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 ...
31 votes
2 answers
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, ...
  • 313
3 votes
1 answer
374 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 ...
  • 457
2 votes
1 answer
228 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 ...