# 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)

69 questions
Filter by
Sorted by
Tagged with
56 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 ...
64 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. ...
86 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 ...
46 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 ...
44 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 ...
77 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 ...
44 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 ...
34 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. ...
20 views

100 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 ...
97 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 ...
52 views

### Universal Turing Machine run on Universal Turing Machine

I am curious, what happens if we run Universal Turing Machine on itself?
105 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 ...
83 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?
253 views

945 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 ...
280 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 ...