23 votes
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 ...
user avatar
21 votes

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 $[1]$, which computes ...
user avatar
  • 5,924
16 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 ...
user avatar
15 votes

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 ...
user avatar
  • 141k
12 votes
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$, ...
user avatar
  • 1,612
11 votes

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? ...
user avatar
  • 70.9k
11 votes

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 ...
user avatar
10 votes
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 ...
user avatar
10 votes
Accepted

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

Arithmetic circuits compute a polynomial in their input. An arithmetic circuit over some field $\mathbb{F}$ with $n$ variables and total degree $d$ can compute functions $f:\mathbb{F}^n\rightarrow\...
user avatar
  • 13.2k
8 votes
Accepted

Convert DFA to Regular Expression

The conversion in each step forms REs that describe The previous direct edge from one state to another and the path(s) that use(s) only the removed state as an intermediate state. In your example, ...
user avatar
  • 6,519
8 votes
Accepted

Why is simulation by non deterministic Turing machine faster than a deterministic one?

First of all, simulation of non-deterministic universal TM is better than simulation of deterministic universal TM only time-wise. But number of parallel executing threads is very high. In parallel ...
user avatar
  • 4,747
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 ...
user avatar
7 votes

Why do we need epsilon-transitions in Thompson's construction?

What you're looking at there is what's known as Thompson's construction. The idea is that any node in the regular expression parse tree corresponds to an NFA with a single entry and exit point. To see ...
user avatar
  • 19k
7 votes

Does the Linz Ĥ applied to ⟨Ĥ⟩ correctly transition to its final reject state?

This is an answer to an attempt at understanding a previous version of the question, and is no longer relevant to the latest question. Your question is: What happens when you use a simulating halt ...
user avatar
  • 141k
6 votes
Accepted

Efficient simulation of an NFA, while preserving the paths to the accept states

There is no need to construct the DFA. Instead, you can construct a dynamic programming table which answers the question "the NFA could be at state $s$ after reading the $k$th prefix of the word" (the ...
user avatar
6 votes
Accepted

What does "fast-forwarding" mean in the context of CPU simulation?

Fast forwarding is used to warm-up microarchitectural state (caches, branch predictors, etc.) in preparation for more accurate simulation of a particular section of interest within an application. ...
user avatar
6 votes
Accepted

What is the difference between Simulated Annealing and Monte-Carlo Simulations?

Monte Carlo simulation is a method for computing a function. Simulated annealing is an optimization heuristic. Other than that, the only common thread behind these two methods is the use of randomness....
user avatar
5 votes
Accepted

Can any recursion implementation be written as tail-recursion?

You can't rewrite all your recursive calls as tail recursive calls but you can rewrite your program in continuation passing style which is closely related and has the feature that every procedure call ...
user avatar
5 votes

Converting this NFA to Turing Machine

A DFA is simply a Turing machine that moves the head to the right on every transition until it reaches the first blank tape cell. Thanks to Ryan for a comment that clarified this answer.
user avatar
5 votes

Rice's theorem vs Turing completeness

I'm not sure I understand your confusion (feel free to expand, if you are still confused), but there two issues that might give you better intuition: Given a Specific TM $M$, we can know ``for sure'' ...
user avatar
  • 20.4k
5 votes
Accepted

Brzozowski algebraic method for NFA

Brzozowski's algebraic method is safe as long as you don't have epsilon transitions. It even works if your transitions are labelled by languages not containing the empty word. It may also work if some ...
user avatar
  • 5,924
5 votes

What does "fast-forwarding" mean in the context of CPU simulation?

Here I will complement the perfectly correct information that Paul gave with more gem5 specifics. One major use case for fast-forwarding is when you have to boot Linux/Android and only then run your ...
user avatar
4 votes
Accepted

Connection of "modern" runtimes and number of steps on a Turing machine

Your premise that turing machines can implement algorithms with the same efficiency as a modern computer is not correct. Turing machines can simulate 'enhanced' turing machines that have the ...
user avatar
4 votes
Accepted

Thompson's Construction Algorithm produces a different NFA

Your construction is correct, in that your FA accepts $(a\mid b)^*$. In fact, the construction is exactly the one that is used in a popular (and very good) text by Peter Linz. However, your instructor ...
user avatar
  • 14.6k
4 votes
Accepted

pda: transformation between acceptance by empty stack and final states

If I am understanding this correctly, you want to transform a PDA with final state acceptance into one that accepts by empty stack. First point is, like you mention, when entering an "old" final ...
user avatar
  • 27.6k
4 votes
Accepted

How would I simulate a network to explore the percolation threshold of a network connected by the knight's move?

First of all, you don't simulate an infinite board. You simulate larger and larger boards, until the percolation threshold seems to stabilize. For a given size of board, you need to decide on what ...
user avatar
4 votes
Accepted

Polynomial hierarchy: inclusion between spaces

Using the definition of Papadimitrou for polynomial hierarchy, or for that matter from wiki, the proof is really simple. $\Delta^P_{k+1} = P^{\Pi_k^P} \subseteq CoNP^{\Pi_k^P} = CoNP^{\Sigma_k^P} = \...
user avatar
  • 4,747
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 ...
user avatar
4 votes
Accepted

Quantum computer simulators with proper measurements

Based on QCAD's help file, their measurement gates are more like measure-later-suggestions: The measurement gates on QCAD only set "measurement flags". After the calculation, the measurement is ...
user avatar
  • 5,722
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 ...
user avatar
  • 28.2k

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