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.
42
questions with no upvoted or accepted answers
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
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
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
0
answers
324
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
2
votes
0
answers
40
views
What was the original paper that showed a simulation of turing machines via circuits?
It is a very standard construction in most complexity theory courses to turn a turing machine into a circuit. I thought this was due to Cook, but it looks like he did the reduction to SAT not through ...
- 332
2
votes
0
answers
61
views
What algorithm to use for substractive machining RT simulation?
For a CAM (Computer Aided Manufacturing) software, and more specifically, for the simulation of the subtractive manufacturing, I would like to understand how to design the representation.
In ...
- 149
2
votes
0
answers
44
views
Understanding the simulate of an IF loop program through a LOOP program
We have the following operation $\text{IF} \ x_i =0 \ \text{THEN} \ P \ \text{END}$. I want to simulate this using a $\text{LOOP}$ program. Here is what I have:
$$\text{IF} \ x_i = 0 \ \text{THEN} \ P ...
- 453
2
votes
0
answers
900
views
Equivalence between different Turing Machines and a definition of simulation
Im having some difficulty understanding how the following two concepts could be related.
Equivalence between TMs as is commonly tought
According to this site answer, to prove a standard TM model to ...
- 21
2
votes
0
answers
167
views
Bisimulation, bisimulation equivalence and simulation equivalence?
I got a little confused with these 3 concepts. Is there a difference between bisimulation and bisimulation equivalence and if yes, then what is it? Also, if we say that the LTS's X and Y are bisimilar,...
- 21
2
votes
0
answers
34
views
Avoiding collisions in space and time
Say I have an image, represented as a 2D array of pixel values. Also, say I have a set of points on that image where each has a current (x, y) position and a Destination (x, y) associated with it. I ...
2
votes
0
answers
126
views
Simulating QC using nondeterministic Turing machine
Is it more efficient to simulate Quantum Computer using a non-deterministic Turing machine?
Would it be more efficient than simulation using a deterministic Turing machine or probabilistic Turing ...
- 259
2
votes
0
answers
34
views
Advantages of block-based simulator versus equation-based simulator
I am mostly using Modelica, an equation-based simulator.
I assume that block-based simulators like Simulink have their strengths and are better at some tasks, but I am wondering what those are. It ...
- 668
2
votes
0
answers
152
views
Proving weak simulation
I want to prove something but I am not sure if it is the right way to do it.
I have two LTS that define different semantics. A=($Q_a,Λ,\to)$, and B=$(Q_b,Λ\cup\{\beta\},\leadsto)$, where $\beta$ is ...
- 121
2
votes
0
answers
72
views
Expressing classic automata in modern terms
This semester I was introduced to finite automata (FSM), then pushdown automata (PDA), and now the Turing machine (TM). Granted that there're many possible implementations of these abstractions (...
1
vote
0
answers
25
views
Learn computer architecture and organisation via an oversimplified machine
I wish to learn CO&A (computer organisation and architecture) from scratch via some toy system and its simulator. I found the following resource: Toy Machine developed at Princeton University.
Toy ...
- 111
1
vote
0
answers
61
views
Why does a kalman filter work better in a simulation than in real life?
I am trying to use a classical
Kalman filter
for getting indoor location. I am using geolocation API of HTML to get
latitude, longitude, position accuracy and speed. I am also using the
smartphone's ...
1
vote
0
answers
757
views
Queries regarding simulation of multi-tape turing machine using single tape turing machine
I was going through the classic text "Introduction to Automata Theory, Languages, and Computation"
by Jeffrey Ullman,John Hopcroft and Rajeev Motwani, where I came across the simulation of MULTI-TAPE ...
- 1,042
1
vote
0
answers
36
views
How to improve convergence to an equilibrium value, & damp oscillation?
I am developing a program which seeks strategies for the players A, B in any of a family of simple 2-player gambling-games. The program iterates, using a genetic algorithm to determine, from the ...
- 111
1
vote
0
answers
129
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
0
answers
227
views
How can an arbitrary Turing machine running for $t$ steps be simulated in $O(n \log(n))$ steps?
I'm confused about a point regarding the Time Hierarchy Theorem. In order to establish the upper bound for this theorem it's necessary to show the following:
We're given $(\langle M \rangle, t)$ ...
- 1,048
1
vote
0
answers
66
views
How to Optimise Each Multithreading Technique? (Cooperative/Preemptive/Simultaneous)
I am currently in the process of writing an IB Extended Essay on the efficacy of multithreading on increasing the performance of applications. So far, I have been able to deduce that there are three ...
- 113
1
vote
0
answers
32
views
How to Simulate Nested Parallelism on a Sequential Machine
So I have sets of functions $A$, $B$, $C$, $D$, $E$, and $F$. I want to run them in a nested way. I also want to run some of them in parallel, and some of them in sequence. Here is how that might look:...
- 2,103
1
vote
0
answers
21
views
Strategy / Technique for Proving Equivalence between Multiple Program Forms
Wondering how to prove different compiled forms of a program to be "effectively the same" or "equivalent".
For example, you can have a program represented as your normal nested function calls, or ...
- 2,103
1
vote
0
answers
126
views
MATLAB script to model biological branching process
I took an introductory MATLAB course a couple of years ago (and since then have only taken a basic C++ course) and am presently stumped as to how to start with a project I am undertaking. As part of ...
- 123
1
vote
0
answers
830
views
Constructing a turing machine from a PDA - dealing with non-determinism
Given a PDA $P$, I believe we can simulate it with a turing machine with 2 tapes - one for keep reading the input and one for the stack.
But, a PDA transition function may have multiple transitions ...
- 327
1
vote
0
answers
110
views
Formal definition of simulation
Assume that the model of computation is a standard Turing machine model with input alphabet $\Sigma = \{0,1\}$, work alphabet $\Gamma = \{0,1,\_\}$, 1 input tape, 1 work tape and 1 output tape.
We ...
- 12.4k
1
vote
0
answers
36
views
Particles-based models - Discrete or Continuous, why?
I have a theoritical question about particles-based simulator (Reeves,83). I don't know if my question is relevant and I apologize if not.
On each frame, the system generate particles and attribute ...
- 131
1
vote
0
answers
139
views
generic technique to build LTL/CTL formula that satisfy specific inputs to a model
I have an automaton, for example the below automaton and would like to generate a single formula (LTL or CTL, or some other representation) that satisfy exactly the traces provided. e.g.,
$t_1 = i^*...
- 203
1
vote
0
answers
36
views
How to make logical inference from simulated data
I have data collected from a computer simulation of football games which seem to have
recurring patterns of the following form.
if madrid plays arsernal and the match ends under 3 goal, then on ...
- 11
1
vote
0
answers
744
views
K -> 2 tape reduction for nondeterministic Turing machines
How to I show that any language in NTIME(T(n)) can be accepted by a non-deterministic 2-tape O(T(n)) time-bounded Turing machine, with modifiable input tape?
I've seen the k to 2 tape reduction for ...
- 51
0
votes
0
answers
37
views
are computer errors inevitable?
this is my First post,I apologize for my ignorance.
The question is:
Could a programmer (human or Ai) with all the computing power and infinite time create a simulation of a world with our same laws ...
0
votes
0
answers
26
views
Looking for a multi-processor job scheduling strategy simulator
I hope this is the appropriate Stack Exchange site for questions like this.
Recently, a college student and I are looking for a robust software for simulating job scheduling in multi-processor ...
- 101
0
votes
0
answers
62
views
Creating An Artificial Universe
This is a general question and one that has bugged me for a long time.
I want to start working on an artificial universe, not something too ambitious but more of a basic concept. What I have in mind ...
- 11
0
votes
0
answers
82
views
Regular grammars
I am fairly new to automata, regular expressions and regular grammar. I am struggling to understand how to define the regular expression (abc)* into one or several regular grammar expressions.
...
- 13
0
votes
0
answers
78
views
Hierarchical Parallel Processing Machines
Introduction
I am wondering if there is a generalization of parallel processing / asynchronous communication that explains/models how to deal with a hierarchy of parallel processes. Mainly looking ...
- 2,103
0
votes
0
answers
75
views
Is it possible for a [futuristic] computer to contain the information of the whole universe?
(This is a question of information theory, data compression and entropy, so I believe it fits CS forum)
Does the fact that the computer itself is a part of the universe make it logically impossible ...
- 71
0
votes
0
answers
56
views
Is it possible to simulate oracle machines on 1-dimensional cellular automata?
My instinctual response is that it is possible, but I can't see how to simulate the oracle tape on a 1-d CA.
If not, are they able to be simulated on n-dimensional CA? My thought is that the oracle ...
- 131
0
votes
0
answers
72
views
Metropolis algorithm Simulated annealing
Someone could explain me in a simple way why Bruce Hayek theorem guarantee an optimal schedule for Metropolis algorithm?
For me is enough an informal explanation.
Thanks.
0
votes
0
answers
964
views
Converting a CFG with epsilons into a DPDA
I have a CFG:
S -> $T$
T -> T+T|T-T|T/T|(T)|CX|I
X -> XX |C|N|_|@
C -> a|b|c|....|z|A|B|C|...|Z|_
N -> 0|1|2|....|9
I -> NI|N
Here @ means epsilon.
The above is a valid arithmetic expression ...
- 101
0
votes
0
answers
200
views
Stepping through a sequence of grouped logic gates
I'm performing a simulation of protein-protein interactions. I'm using Python to code logic gates as functions to model protein interactions.
My model is basically a series of groups (...
0
votes
0
answers
32
views
Name for a Type of Simulation
I have come up with a type of simulation "game" but I cannot find anything describing it online.
The simulation has a 2D "world" with a number of automatons on a discrete grid, similar to the game ...
- 141
-2
votes
1
answer
85
views
How can I convert a Grammar to NFA?
Hello I have a task where I´m stucking at.
I have to convert a Grammar to NFA. I have these information:
G=(V,T,P,S) V={S}, T{0} and
S -> 0S
S -> 0
I can´t ...
- 11