48
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 ...
- 18.2k
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$-...
- 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 ...
- 82.1k
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. ...
- 8,323
26
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, ...
- 82.1k
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 ...
- 8,323
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 ...
- 710
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 ...
- 13.5k
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 ...
- 72.8k
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 ...
- 31k
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 ...
- 1,241
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 ...
- 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.♦
- 164k
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 ...
- 151
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
...
- 310
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",...
- 9,877
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 ...
- 3,553
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, ...
- 173
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.
...
- 278k
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 ...
- 516
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 ...
- 5,776
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 ...
- 1,191
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.
- 1,778
4
votes
To what extent is an x86 machine equivalent to a Turing Machine?
For a real computer, everything is decidable. There is a (far bigger than astronomically but) finite number of possible states, so any program will eventually halt or enter the exact same state a ...
- 31.4k
4
votes
How do we define the term "computation" across models of computation?
Definition 5.12 is a standard way of defining a "computable function". I see that you wish it was defined generically, but things are not as you wish they were; computability is typically ...
D.W.♦
- 164k
4
votes
Accepted
Does Nondeterministic TM is a counterexample of Extended Church-Turing Thesis?
No, because nondeterministic Turing machines are not "reasonable" in the sense used here. In this context, the ECT talks about realistic models of computation, i.e., models that can be ...
D.W.♦
- 164k
3
votes
Is a Turing machine too strong of a model to model physical computation?
No, the Turing machine isn't unreasonably strong. You could build a physical Turing machine by giving it a finite length of tape and the ability to say "I've run out of tape – please give ...
- 82.1k
3
votes
weak Church-Turing thesis
You are asking two questions. The answer to your first question, for models stronger than Turing computation, is the field of hypercomputation. The answer to your second question, asking for evidence ...
- 278k
3
votes
Would any continuous model of the universe have/be based on hypercomputational laws?
If you are interested in the effect of being able to compute with continuous real numbers, you might enjoy learning about the Blum-Shub-Smale theory of computation with the reals. A good survey is ...
D.W.♦
- 164k
3
votes
Why is nondeterminism physically not realizable?
Is it possible to make a machine that when it encounters a non-deterministic step it takes an arbitrary one? Yes easily.
Will this machine be able to solve NP problems in P? No because it will most ...
- 4,646
Only top scored, non community-wiki answers of a minimum length are eligible