47 votes
Accepted

Church-Turing Thesis and computational power of neural networks

No, it's still consistent with the Church-Turing thesis, their model comes equipped with genuine real numbers (as in arbitrary elements of $\mathbb{R}$), which pretty much immediately extends the ...
Luke Mathieson's user avatar
45 votes
Accepted

Do any programming languages use general recursive functions as their basis?

Direct answer to the question: yes, there are esoteric and highly impractical PLs based on $\mu$-recursive functions (think Whitespace), but no practical programming language is based on $\mu$-...
xuq01's user avatar
  • 1,190
29 votes
Accepted

Can every self-modifying algorithm be modelled by a non-selfmodifying algorithm?

Yes, it's possible. You can simulate the program by using an interpreter for the language it's written in. Now, the program (the interpreter) is fixed and the thing that used to be a self-modifying ...
David Richerby's user avatar
28 votes
Accepted

Turing machine + time dilation = solve the halting problem?

Note that Turing's proof is one of mathematics, not of physics. Within the model of a Turing machine Turing defined, undecidability of the halting problem has been proven and is a mathematical fact. ...
Discrete lizard's user avatar
  • 8,248
26 votes

Is there any uncountable Turing decidable language?

Every language over a finite (or even countable) alphabet is countable. Assuming your Turing machine alphabet is finite, any language it can possibly accept is countable.
Yuval Filmus's user avatar
25 votes

Church-Turing Thesis and computational power of neural networks

To expand a little on Luke's answer, physically building a neural net to solve any language requires producing electronic components with infinitely precise resistances and so on. This isn't possible, ...
David Richerby's user avatar
18 votes

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

First of all, quantum computers (or rather, theoretical quantum computation models), are in fact, not more powerful than Turing machines, in the sense that they can be emulated on a Turing machine and ...
Discrete lizard's user avatar
  • 8,248
17 votes
Accepted

Would creating a complete computer simulation of the human brain prove the Church-Turing thesis?

How would you prove that the machine is faithfully simulating a brain? How would you prove that it doesn't matter if you simulate my brain or your brain or somebody else's brain? Church–Turing ...
David Richerby's user avatar
16 votes
Accepted

Is there any uncountable Turing decidable language?

We can have uncountable languages only if we allow words of infinite length, see for example Omega-regular language. These languages are called $\omega$-languages. Another example will be language of ...
Sarvottamananda's user avatar
14 votes
Accepted

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

There are many different meanings of the word "can". Is there an algorithm that can break AES-512 encryption? One strategy would be to take all 2^512 possible blocks of 512 bits, encrypt all of them ...
Acccumulation's user avatar
10 votes

Can every self-modifying algorithm be modelled by a non-selfmodifying algorithm?

Any Turing-complete computational model that does not have modifying code (or "code") serves as a proof of that statement. I don't know that any of the standard models (TM, RAM, ...) do have modifying ...
Raphael's user avatar
  • 72.4k
10 votes

Turing machine + time dilation = solve the halting problem?

The Turing machine is a formal mathematical model of computation, it does not answer to any physical limitations and does not care about relativistic effects. This means that Turing's proof does not ...
Ariel's user avatar
  • 13.4k
8 votes

Turing machine + time dilation = solve the halting problem?

Turing’s proof shows that no Turing machine can solve the Halting Problem no matter how much time you give it. If your spaceship used time dilation to give a computer a billion years to work, it ...
Davislor's user avatar
  • 1,241
8 votes
Accepted

Does computability according to Church-Turing thesis include side effects?

The Church-Turing thesis says that Turing machines capture precisely the effectively calculable functions from natural numbers to natural numbers. It says little about what happens when we attach a ...
Andrej Bauer's user avatar
  • 30.4k
7 votes

Would creating a complete computer simulation of the human brain prove the Church-Turing thesis?

Part of the issue with the idea of "proving" the Church-Turing thesis is that the Church-Turing thesis isn't a precise mathematical statement. Rather, it's the idea, or "belief" if you will, that any ...
templatetypedef's user avatar
7 votes
Accepted

Can current quantum computers decide languages that Turing Machines cannot?

No. A state of $n$ qubits can be represented with a vector of size $2^n$, and quantum gates can be implemented as linear operations for those vectors. Therefore a quantum computer can be simulated ...
Laakeri's user avatar
  • 1,339
6 votes

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

The difference is: since x86 machines are finite, Turing machines can decide languages (decision problems) that cannot be decided by any x86 machine. As I explained before, the idea of 'the set of ...
D.W.'s user avatar
  • 159k
5 votes

Is there any uncountable Turing decidable language?

Classical computability discusses functions over finite strings from a finite alphabet. As a result all languages whether decidable or undecidable are countable. To consider uncountable languages we ...
Kaveh's user avatar
  • 22.2k
5 votes
Accepted

The Church-Turing-Thesis in proofs

A Turing machine provides a formal definition of a "computable" function, while the Church-Turing-Thesis says that intuitive notion of "computable" coincides with the formal definition of "computable",...
fade2black's user avatar
  • 9,837
5 votes

Turing machine + time dilation = solve the halting problem?

An objection is that you have defined a process that can produce infinite entropy in a compact region and that appears to do so in a finite segment of the observer's past. This means a few things ...
Eric Towers's user avatar
5 votes

Do any programming languages use general recursive functions as their basis?

Typing µ-recursive function programming language in Google led me to this GitHub repo, so the answer to your question is: Yes, and it's called myopia It's ...
Kapol's user avatar
  • 151
5 votes

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

I see two ways of interpreting this question, but the answer is essentially trivial either way. Interpretation 1: Can every hypercomputation model decide some language that cannot be decided by a ...
Aaron Rotenberg's user avatar
5 votes
Accepted

Kleene's Theorem and TMs

We can prove the following theorem: Theorem: A language $L$ is regular if and only if there exists a DFA or NFA for language $L$. Turing machines are more powerful than DFAs and NFAs. In particular, ...
Sepehr Omidvar's user avatar
5 votes
Accepted

The Church-Turing thesis and Hyper-computation

The Church–Turing thesis is about physically realizable machines. To the best of our knowledge, hypercomputation models cannot be realized in the physical world. They are a figment of our imagination. ...
Yuval Filmus's user avatar
4 votes

Can every self-modifying algorithm be modelled by a non-selfmodifying algorithm?

To add on to David Richerby's answer: If it were true that no self-modifying algorithms can't be modeled by non-self-modifying algorithms, then those algorithms would have to be executed on something ...
Alexander's user avatar
  • 516
4 votes

Would creating a complete computer simulation of the human brain prove the Church-Turing thesis?

No, that wouldn't prove the thesis. Human beings are allowed to use machines. For example, an important consequence of the Church-Turing thesis is that computers can only compute Turing-computable ...
Yuval Filmus's user avatar
4 votes

Church-Turing and physical PDEs

The branch of mathematics and computer science that studies these questions is computable mathematics. The general answer is that things tend to be computable. I would add to that the observation that ...
Andrej Bauer's user avatar
  • 30.4k
4 votes

Is a Turing machine too strong of a model to model physical computation?

Is it too strong? The concern should not be that a Turing machine is a too strong model because of the way we construct a Turing machine. Turing machine is essentially a framework for defining a ...
Sandro Lovnički's user avatar
4 votes
Accepted

Is a Turing machine too strong of a model to model physical computation?

No, it is not too strong. We fundamentally conceive of computation as an activity with unlimited resources. For instance, take a very popular and simple algorithm such as long division. It takes two ...
reinierpost's user avatar
  • 5,529
4 votes

Are Linear Bounded Automatons Turing Complete?

A linear bounded automaton is a Turing machine that runs on input of size $n$ in $\mathcal{O}(n)$ space. By the space hierachy theorem there exist languages that need e.g. $\omega(n^2)$ space.
ttnick's user avatar
  • 1,621

Only top scored, non community-wiki answers of a minimum length are eligible