Questions tagged [simulation]
Questions about simulating one model in another. This includes simulating reality in any model, or simulating a machine model with Turing machines.
33
questions
14
votes
3
answers
24k
views
How to create DFA from regular expression without using NFA?
Objective is to create DFA from a regular expression and using "Regular exp>NFA>DFA conversion" is not an option. How should one go about doing that?
I asked this question to our professor but he ...
user4220128
23
votes
3
answers
8k
views
How to show two models of computation are equivalent?
I'm seeking explanation on how one could prove that two models of computation are equivalent. I have been reading books on the subject except that equivalence proofs are omitted. I have a basic idea ...
- 3,678
16
votes
1
answer
2k
views
Universal simulation of Turing machines
Let $f$ be a fixed time-constructable function.
The classical universal simulation result for TMs (Hennie and Stearns, 1966) states that there is a two-tape TM $U$ such that given
the description of ...
- 22.2k
3
votes
2
answers
10k
views
Prove Queue Automaton is equivalent to Turing Machine
A deterministic queue automaton (DQA) is like a PDA except the stack is replaced by a queue. A queue is a tape allowing symbols to be written (push) on the left-end and read (pull) on the right-end.
...
- 345
19
votes
2
answers
5k
views
How can I convert the Turing machine the recognizes language $L$ into an unrestricted grammar?
According to this Wikipedia article, unrestricted grammars are equivalent to Turing machines. The article notes that I can convert any Turing machine into an unrestricted grammar, but it only shows ...
- 375
9
votes
2
answers
5k
views
Infinite alphabet Turing Machine
Is a Turing Machine that is allowed to read and write symbols from an infinite alphabet more powerful than a regular TM (that is the only difference, the machine still has a finite number of states)?
...
- 298
4
votes
1
answer
472
views
Proof that PDA's with different definitions have same expressive power
Let $P$ be a push down automaton $(Q,\Sigma,\Gamma,\delta,q_s,F)$,
where
$Q$ is the set of states,
$\Sigma$ is the input alphabet
$\Gamma$ is the stack alphabet
$\delta$ is the transition function ...
- 43
3
votes
1
answer
4k
views
Right moving turing machine
I am interested in simulating any turing machine with a turing machine that is allowed only to move right. I guess that it should be pretty standard material and likely it is trivial (or known to be ...
- 165
15
votes
4
answers
972
views
Is every linear-time algorithm a streaming algorithm?
Over at this question about inversion counting, I found a paper that proves a lower bound on space complexity for all (exact) streaming algorithms. I have claimed that this bound extends to all linear ...
- 72k
9
votes
1
answer
27k
views
Convert CFG to PDA
Is there any set of rules or methods to convert any context free grammar to a push down automata?
I already found some slides online but I wasn't able to understand them.
In slide 10 he speaks ...
- 227
6
votes
1
answer
2k
views
pda: transformation between acceptance by empty stack and final states
I am stuck with understanding the transformation of final-state acceptance automaton into empty-stack acceptance automaton. From everywhere that I've read, it always says introduce a new start state ...
- 63
5
votes
1
answer
4k
views
Multitape Turing machines against single tape Turing machines
Introduction: I recently learned that a multi-tape Turing Machine $\text{TM}_k$ is no more "powerful" than a single tape Turing machine $\text{TM}$. The proof that $\text{TM}_k \equiv \text{TM}$ is ...
- 765
12
votes
1
answer
1k
views
Prove that a boolean function computable in T(n) by a RAM machine is in DTIME(T(n)^2)
The question is exercise 1.9 from Arora-Barak's book Computational Complexity — A Modern Approach:
Define a RAM Turing machine to be a Turing machine that has random access memory. We formalize this ...
- 483
7
votes
1
answer
34k
views
Steps to convert regular expressions directly to regular grammars and vice versa
I came across following intuitive rules to convert basic/minimal regular expressions directly to regular grammar (RLG for Right Linear Grammars, LLG for Left Linear Grammars):
Then I came across many ...
- 1,745
6
votes
0
answers
2k
views
Prove that turing machines and the lambda calculus are equivalent
It is known that a turing machine and the lambda calculus are equivalent in power. I now want to try to prove this myself. I think proving that the lambda calculus is at least as powerful as a turing ...
- 69
6
votes
3
answers
1k
views
Would creating a complete computer simulation of the human brain prove the Church-Turing thesis?
According to Wikipedia, the Church-Turing thesis "states that a function on the natural numbers is computable by a human being ignoring resource limitations if and only if it is computable by a Turing ...
- 245
5
votes
1
answer
2k
views
Why is simulation by non deterministic Turing machine faster than a deterministic one?
A deterministic universal Turing machine $U_D$ can simulate a deterministic turing machine $M_D$ in $O(T(n)log(T(n)))$ where $M_D$ runs in $O(T(n))$. But I came across an exercise in Sanjeev Arora and ...
- 2,932
5
votes
2
answers
2k
views
Does every turing machine have an equivalent, single-state, n-tape turing machine?
Is it the case that every problem computable by a Turing Machine can also be represented by some kind of equivalent n-tape Turing Machine which one has only one state? (We can assume that the accept ...
- 461
5
votes
1
answer
437
views
For the time hierarchy theorem, how is the input translated efficiently?
I'm trying to understand the proof of the time hierarchy theorem appearing in sipser's book. The proof requires a TM M to simulate an arbitrary TM N without too much slowdown. In particular, it is ...
- 51
5
votes
1
answer
1k
views
How to simulate a bidirectional TM on a regular one with time factor four?
In Computational Complexity A Modern Approach, one claim says that if $f$ is computable in time $T(n)$ by a bidirectional TM $M$, then it is computable in time $4T(n)$ by a unidirectional TM $\tilde{M}...
- 101
5
votes
1
answer
1k
views
How to convert a Turing Machine program to a tiling using Wang Tiles?
This is a cross-post from a post on MathSE due to lack of answers.
To illustrate my question I provide the following example.
The website Online Turing Machine provides a Turing Machine simulator. ...
- 153
4
votes
1
answer
409
views
Simulate NPDAs with DTMs using only polynomial overhead
We know by polynomial-time parsing algorithms like the classical CYK algorithm that $\mathrm{CFL} \subseteq \mathrm{P}$.
Furthermore, it is easy to show by direct simulation that $\mathrm{DCFL} \...
- 72k
3
votes
0
answers
335
views
Context free grammar as minimal solution of a system of equations
It is a well-known fact that language generated by a context-free grammar is the minimal solution of a particular system of equations, for example:
$$\begin{align*}
X &=\{{\epsilon}\} \cup Y\\
X ...
- 203
3
votes
3
answers
831
views
Rice's theorem vs Turing completeness
I would like to clarify this because I see some kind of contradiction between Rice's theorem and Turing completeness.
This is the problem:
In building an Universal Turing Machine to emulate another ...
- 703
3
votes
2
answers
2k
views
Mealy to Moore Conversion
Consider an $m$ output, $n$ state Mealy machine. How many states does the equivalent Moore machine contain?
The answer is $mn$ but my argument is that the total number of output produced while ...
- 75
2
votes
2
answers
768
views
If a DFA can be simulated by a real program, can it be simulated by a TM
In proofs of decidability, we often want to simulate another model of computation by a Turing machine. But if I can simulate a $\mathsf{DFA}$ by, say, a C program, then is there some result which says ...
- 269
2
votes
1
answer
5k
views
Converting final state PDA to empty stack PDA
I'm having a problem understanding this conversion. Let's say we have a CFL like this:
$ { a^nb^m : n > m } $
A final state acceptance PDA for this language would push $A$ symbols in the stack for ...
- 225
2
votes
1
answer
699
views
Space requirement of a universal Turing machine
Given a representation $g$ (e.g. the Gödel number) of a Turing machine $B$, a universal Turing machine $A$ can simulate $B$.
If $B$ is restricted to using at most $n$ memory cells of its tape and the ...
- 187
1
vote
0
answers
134
views
MAX-CUT: are there any algorithms or codes for classical computers, that cater to this specific case?
A paper was published recently in Science where the authors minimized the following function:
$$E_{\text{Ising}}(s) = -\dfrac{1}{2} \Sigma_{i=1}^{N} \Sigma_{j=1}^{N} J_{i,j} s_i s_j,$$
where $s_i$ ...
- 237
1
vote
2
answers
434
views
Variant of Turing machine
How to prove that standard Turing machine is equivalent to a variant model where a string is accepted if the machine enters an accept state during computation? However, the machine may leave the ...
- 21
1
vote
1
answer
1k
views
Prove Halting on all Inputs is not in RE simulation
I don't understand why when proving if Halting on all inputs problem si not in RE using the complement of the halting problem, I have to take a turing machine and simulate the machine M(the machine ...
- 13
1
vote
2
answers
107
views
How to prove a side effect in a function
I asked a question earlier about Saving to the Database, which was very general and about the requirements for a proof when you go through many layers of non-verified systems such as the network and ...
- 2,163
0
votes
1
answer
254
views
Connection of "modern" runtimes and number of steps on a Turing machine
Why an evaluation of Turing machine efficiency is equal to the algorithm which is implemented by this machine and vise versa? For example, we can say that efficiency of merge sorting algorithm is O(...
- 63