21

You show that either model can simulate the other, that is given a machine in model A, show that there is a machine in model B that computes the same function. Note that this simulation does not have to be computable (but usually is). Consider, for example, pushdown automata with two stacks (2-PDA). In another question, the simulations in both directions ...


21

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 quantum gate modifies those distributions as time progresses. This isn't very efficient (which is why people want to build actual quantum computers) but it works.


19

An answer shamelessly copied from myself: A multi-tape Turing Machine is mostly the same as a single-tape machine, except we have an extended transition function $Q\times\Gamma^{k}\rightarrow Q\times\Gamma^{k}\times\{L,R\}^{k}$ where $k$ is the number of tapes. So in each state, the transition function reads the contents of each tape, moves to a new state, (...


19

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 directly the Nerode automaton of a language (which is known to be equal to its minimal deterministic automaton). It is based on a direct computation of the ...


17

No, it would be more powerful. The transition function would no longer be finite, and that buys you a lot of power. With an infinite alphabet, you can encode any input item from an infinite set in one symbol (although the input set can't be "more infinite" than the alphabet set, e.g. the alphabet would presumably be only countably infinite, so elements of ...


16

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 isn't something that can be proven. It's essentially just the statement that Turing machines correspond to the intuitive notion of algorithm and that just isn't ...


15

For streaming algorithms to be meaningful, they have to work with significantly smaller amount of work space than the input itself. For example, if you allow the same amount of work space as the input, then you can trivially state any algorithm as a “single-pass streaming algorithm” which first copies the input to the work space in single pass and then only ...


14

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 polynomial $p(x_1,\dots,x_n)$ such that $f(x_1,\dots,x_n) = p(x_1,\dots,x_n)$ for all $x_1,\dots,x_n$, where arithmetic is done modulo two (i.e., over the field $\...


11

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? can not be generally and algorithmically decided for the reasons you state. However, we can prove for a fixed Turing machine that it is universal -- and that ...


11

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 thesis Turing completeness includes all functions which can be calculated using any mechanical process. So if this thesis is true, any computer you could possibly ...


10

Look at the original paper by Hennie and Stearns: F.C. Hennie and R.E. Stearns, "Two-Tape Simulation of Multitape Turing Machines", Journal of the ACM (JACM), Volume 13 Issue 4, Oct. 1966, pp. 533-546 The construction is a little bit elaborate, but not extremely difficult to understand. The basic idea is to store and keep the current symbol of each tape in ...


10

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 numbers ("State 1", "State 2", "State 3", etc.). Even with just two non-blank characters, the universal machine can represent all those integers as binary strings. ...


10

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\mathbb{F}$ of the form: $$f(x_1,...,x_n)=\sum\limits_{i_1+...+i_n\le d}\alpha _{i_1,...,i_n}\cdot x_1^{i_1}x_2^{i_2}...x_n^{i_n}$$ where $\alpha _{i_1,...,i_n}\...


10

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$, we would write $b$, move in direction $r$, and transition to state $S_m$. We will allow our machine to move left, right, or stay in place ($<$, $>$, or $...


9

We encode the Turing machine's tape content in sentential forms; a special set of non-terminals encodes the current state. There can only be one of them in the sentential form at any point in time, placed to the right of the symbol the TM is currently pointing at. The second crucial idea is that we have to reverse the process: TMs take the word as input and ...


9

That very much depends on how well the instruction set of the CPU to be emulated maps to the instruction set of the emulating CPU. Certainly, clock speed is not the deciding factor. It might very well be that a slower (clock wise) CPU A can emulate a faster CPU B. This can be both because of more powerful instructions (e.g. SSE instructions that allow doing ...


8

As for a $\mu$-calculus formula not expressible in CTL*, see this post. As for texts on the subject, you are likely to get further ahead by reading papers, as these topics are not covered in many books. Still, the Handbook of Modal Logic may be a good start. As for papers, try: Expressive power of Temporal Logics This PhD thesis Emerson's Model checking ...


8

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, the path for $aa$ goes through $q_1$, which is not removed in this step. Thus it is not added to the RE.


7

I'm referring here to the proof of the hierarchy theorem as I am familiar with it, in which I don't see the problem you mention. We define the language $L=\{(M,w): M $ does not accept $(M,w)$ within $\le \frac{t(n)}{|M|^3+|M|\log t(n)}, n=|(M,w)|\}$ (where $t$ is the time function we are working on). We show that $L$ is decidable in $O(t(n))$ using the ...


7

What is the best known simulation result on a single tape TM? Does the result above also still hold? We can simulate a multiple-tape TM on a single-tape TM with quadratic increase in time. The simulation time is $O(n^2)$. The quadratic increase is required since there are languages (e.g. palindromes) that require time $\Omega(n^2)$ on a single-tape DTM but ...


7

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 model of computation that could feasibly be constructed is either equal in power to a Turing machine or weaker than a Turing machine. If we were to try to ...


6

In the streaming model you are only allowed to store constant or poly-logarithmic extra-data while scanning through the input. If you consider a linear time algorithm that follows the divide and conquer paradigm, you need to store more information and/or you should scan through your data as many times as the depth of the recursion. One example is the DC3 ...


6

The above answer is correct, but there is a little more that can be said about infinite alphabets and computability. A Turing Machine is described in WP as $M = (Q, \Gamma,b,\Sigma,\delta, q_0, q_f)$ in which all sets are finite. Thus the transition function $$ \delta: Q / F \times \Gamma \rightarrow Q \times\Gamma \times \{L,R \} $$ is necessarily ...


6

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 parameters are both $s$ and $k$). In order to efficiently fill this table in the presence of $\epsilon$-transitions, you need to compute ahead of time the ...


6

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 algorithms parlance, $T(n)$ will be smaller but another metric $T(n)P(n)$ will be higher. Deterministic UTM has extra $\log T(n)$ factor because it has to ...


6

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 why the epsilon transitions are useful, try applying the construction to, say, $(a \cup b^*)c$. Thompson's construction is particularly easy to understand and ...


6

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. Since microarchitectural state can depend on operation ordering (e.g., cache replacement for data accesses and interactions between threads), speculation (e.g., ...


5

Cornell's Conway, Johnson and Maxwell's paper Some Problems in Digital Systems Simulation, was published in 1959 in Management Science. It discusses many of the key points of a discrete event simulation, including managing the event list (they call it an element-clock) and refer to "more efficient but more complicated methods" for locating the next event, ...


5

The deterministic machine simulates all possible computations of a nondeterministic machine, basically in parallel. Whenever there are two choices, the deterministic machine spawns two computations. This proces is sometimes called dovetailing. The tape of the deterministic simulator contains a list of configurations of the nondeterministic one, and performs ...


5

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'' what it does for all inputs. This is not "sure" in an algorithmic way, but sure in an absolute (mathematical) way. Example: Consider the TM that has ...


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