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.
175
questions
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,650
19
votes
2
answers
4k
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
18
votes
5
answers
7k
views
Why is a quantum computer not capable of solving more problems than a classical computer? [duplicate]
On the Wikipedia page for quantum algorithm I read that
[a]ll problems which can be solved on a quantum computer can be solved on a classical computer. In particular, problems which are undecidable ...
- 305
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 ...
- 21.9k
15
votes
4
answers
955
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 ...
- 71.7k
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
13
votes
1
answer
25k
views
How to map the tapes of a "k-tape" Turing Machine into the single tape of a "1-tape" Turing Machine
I'm reading Sipser and I'm finding it hard to understand what the process is such that if you give me k Turing machines with k tapes, I can spit out an equivalent Turing machine with only one tape. An ...
- 431
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
11
votes
3
answers
3k
views
Why use $\mu$-calculus and not LTL,CTL,CTL*?
It is known that the temporal logics LTL,CTL,CTL* can be translated/embedded into the $\mu$-calculus. In other words, the (modal) $\mu$-calculus subsumes these logics,
(i.e. it is more expressive.)
...
- 129
11
votes
1
answer
2k
views
Time Complexity of Universal Turing Machine Simulations and the Time Hierarchy Theorem
I have a little problem to understand the proof of the Time Hierarchy Theorem (Hennie and Stearns, 1966) that ensures the existence of a language acceptable in $U(n)$ but not acceptable in $T(n)$ for ...
- 696
11
votes
2
answers
397
views
1/r attractive force by cellular automaton
Does there exist a cellular automaton (in 2D) which simulates a $1/r$ force between particles?
More specifically, I would like to know whether it is possible, with strictly local update rules, to ...
- 111
10
votes
1
answer
2k
views
How can a universal Turing machine simulate "bigger" ones?
I'm trying to find the answers of two questions about the Universal Turing machine.
How can the Universal Turing machine simulate a Turing machine if
the one that is being simulated has a bigger ...
- 275
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
9
votes
1
answer
26k
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
8
votes
1
answer
200
views
Church-Turing and physical PDEs
When I read about the Church-Turing thesis it seems to be a common claim that "physical reality is Turing-computable." What is the basis for this claim? Are there any theoretical results along these ...
- 181
8
votes
0
answers
152
views
Make a tag system simulate a finite automaton?
Tag systems are Turing-complete. I was wondering if there is any easy way to create tag systems that simulate finite automata. So create tag systems that recognize languages, e.g. by having at the end ...
- 181
7
votes
3
answers
31k
views
Convert DFA to Regular Expression
In this old exam-task I don't understand all the steps to convert the DFA below to a Regular Expression. The $q_2$ state is eliminated first.
The provided solution to eliminate $q_2$ is:
If we first ...
- 73
7
votes
1
answer
32k
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
7
votes
1
answer
293
views
Simulate the concatenation of two log-space programs in log-space
I've got two log-space programs $F$ and $G$.
Program $F$ will get input in array $A[1..n]$ and will create the output array $B[1..n]$.
Program $G$ will get as input $B$ as created by $F$ and create ...
user12392
7
votes
1
answer
622
views
Relation between RAM and Turing machine
Denote $D$ a set of finite sequences of integers. In Papadimitriou's "Computational Complexity" in theorem 2.5 it is proved that if a RAM program $\Pi$ computes a function $\phi$ from $D$ to integers ...
- 223
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
6
votes
2
answers
1k
views
Does there exist an equivalent arithmetic circuit for each computable function?
Does there exist an equivalent arithmetic circuit for each computable function?
I've been trying to wrap my head around the statement above, but haven't found a counter example although I believe ...
- 501
6
votes
1
answer
198
views
Who conceived the concept of Discrete Event Simulation, and when?
I'm trying to trace back the origin of the general concept of Discrete Event Simulation and found a 1968 article by Fishman and Kiviat mentioning the term. It is titled The statistics of discrete-...
- 1,755
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
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
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
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
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,923
5
votes
2
answers
4k
views
What is the difference between Simulated Annealing and Monte-Carlo Simulations?
What is the difference between Simulated Annealing and Monte-Carlo Simulations? Is Simulated Annealing a specific type of Monte-Carlo simulation, or are they completely separate techniques?
- 467
5
votes
1
answer
2k
views
Brzozowski algebraic method for NFA
Currently I have a graph (basically, a state graph) in Scala which is similar to an NFA
some nodes have multiple in/outgoing edges
single start state
there might be multiple final states
a state can ...
- 103
5
votes
1
answer
157
views
How would I simulate a network to explore the percolation threshold of a network connected by the knight's move?
"If we consider the squares of an infinite chess board as nodes of our graph and consider each to be connected to the other eight squares that are a knight's move away from it what is the percolation ...
- 153
5
votes
1
answer
50
views
Can we always reduce the weights of a weighted graph to rationals and preserve equality relationships?
Let $G = (Q, \Delta, W)$ be a finite weighted graph with $\Delta: Q \times Q$ and $W: Q \times Q \to \mathbb{R}^{+}$. Is it the case that there always exist a function $W': Q \times Q \to \mathbb{Q}^{+...
- 797
5
votes
3
answers
3k
views
Can any recursion implementation be written as tail-recursion?
Can any method that uses recursion be written as tail-recursion?
- 153
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
5
votes
1
answer
2k
views
Oblivious Universal Turing Machine in O(T log(T)) time
I'm currently reading Computational Complexity: A Modern Approach. In this book, they give a proof of a universal Turing machine $U$ such that if $M(x)$ runs in $T$ steps, then $U(\lfloor M \rfloor, x)...
- 151
5
votes
1
answer
432
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
4
votes
2
answers
1k
views
What does "fast-forwarding" mean in the context of CPU simulation?
I'm using a simulator for my thesis and I've come across the term "Fast-forwarding" but I have found no definition anywhere in the documentation or online. From a pdf I've been reading about the ...
- 259
4
votes
2
answers
1k
views
Efficient simulation of an NFA, while preserving the paths to the accept states
The standard way of simulating an NFA on a computer (for implementing regex engines etc) is to construct a DFA that accepts the same language. Otherwise you get problems like exponential blowup.
...
- 357
4
votes
1
answer
456
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
4
votes
1
answer
3k
views
How does a single-track Turing machine simulate a multi-track Turing machine?
It's easy to see how a multi-track Turing machine can simulate a single-track Turing machine; it does so by ignoring all but the first track. But how does it work the other way? I need a specification ...
- 3,650
4
votes
2
answers
4k
views
DFA to regular expression how to deal with 'sink state'
Didn't find a clear statement on this so I just want to make sure I'm right. If I have DFA with edges leading to a 'sink state' (non-accepting state we don't get out of) the edges leading to the sink ...
- 141
4
votes
1
answer
313
views
Converting generalized NFAs to NFAs
I came across generalized nondeterministic finite automata (GNFAs) in Sipser's Introduction to the Theory of Computation. These are automata where transitions are labelled with regular expressions, ...
- 175
4
votes
1
answer
397
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} \...
- 71.7k
4
votes
1
answer
2k
views
On-line simulation of a two-head tape Turing machine using single-head tape(s)
I have a question and I haven't been able to figure out the answer yet. I need to do the on-line simulation of a two-head tape Turing machine using single-head tape(s). I've found some online articles ...
Parsa Rastegari
4
votes
1
answer
104
views
Research work on computational models for a "specific" person's behaviors
Is there active research work on creating computational models of a "specific" person's behaviors (general behaviors, emotions, actions...)? What are some references for such research? I tried google ...
- 161
4
votes
0
answers
49
views
Are there any probabilistic models of computation that can strongly simulate themselves?
I was reading this question over on the quantum computation stackexchange, and the top answer stated that you can't (strongly) simulate even a probabilistic turing machine, on itself. I was just ...
- 193
3
votes
3
answers
811
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 ...
- 693
3
votes
1
answer
895
views
Is it impossible to truly emulate a system if its actual clock speed is the same?
As I understand emulation a rule of the thumb says that a computer must be around a order of magnitude more powerful to emulate another system without resorting to tricks. This is because for every ...
- 133
3
votes
2
answers
1k
views
Robustness of Turing Machines - 3 dimensional case
How can one show that a machine with a three dimensional memory arranged in an infinite grid can be simulated by a single-tape Turing machine? I'd imagine there's some sort of mapping possible from ...
Sebastian