# Tag Info

Accepted

### Why is a quantum computer not capable of solving more problems than a classical computer?

Because a quantum computer can be simulated using a classical computer: it's essentially just linear algebra. Given a probability distribution for each of the qubits, you can keep track of how each ...

### How to create DFA from regular expression without using NFA?

Since you want "to convert regex to DFA in less than 30 minutes", I suppose you are working by hand on relatively small examples. In this case you can use Brzozowski's algorithm $$, which computes ...
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 ...

### Does there exist an equivalent arithmetic circuit for each computable function?

Any computable boolean function with a fixed-length input can be computed by an arithmetic circuit. Consider any boolean function $f:\{0,1\}^n \to \{0,1\}$. Then there exists a multivariate ...
Accepted

### Does every turing machine have an equivalent, single-state, n-tape turing machine?

Yes, there always exists a machine, and we really only need 2 tapes. Your standard TM transition might be written: $\delta(S_n, a) = (S_m, b, r)$ This would mean that, from $S_n$, if we read $a$, ...

### Rice's theorem vs Turing completeness

Your misunderstanding is: 'sure' in the sense of being computationally verified by an algorithm We are not, and we can not be . The question, Is this given Turing machine $M$ a universal one? ...

### Why is a quantum computer not capable of solving more problems than a classical computer?

Classical computers are already Turing complete, i.e. they can calculate everything that a Turing machine can (a theoretical computer model from Computer Science). According to the Church–Turing ...
Accepted

### How can a universal Turing machine simulate "bigger" ones?

The answer to both subquestions is the same: by using the tape to store the necessary data. We can assume that the state set and alphabet of the machine to be simulated are subsets of the natural ...
Accepted

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