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.

Filter by
Sorted by
Tagged with
0
votes
0answers
9 views

Using FFT in the following convolution in a simulation

I have the following convolution as part of a numerical simulation. $$T(r)=\int d^3r_2 p(r_2)f(r_2)\alpha(r-r_2)$$ My problem is that the analytical expressions for $f$ and $p$ do exist but, I have ...
0
votes
1answer
45 views

How would one simulate the law of conservation of energy?

I'm new to computer science, but I've studied physics for a while. I'm just curious, if one wanted to make a simulation of the law of conservation of energy, on a large scale, how would it be done? ...
2
votes
1answer
52 views

Is it reasonable to model row buffers in DRAM corresponding to the same bank ID as one big row buffer?

I'm creating a simple row buffer simulator to go along with a simple cache simulator in order to count hits and misses in the row buffer. Whenever a cache block isn't in the cache I want to go look ...
3
votes
1answer
29 views

Why do we simulate the universal TM to simulate another TM M instead of simulating M directly?

In the proof of the time hierarchy theorem given on page 69 of Arora-Barak, we define a TM D as follows: "On input $x$, run for $|x|^{1.4}$ steps the Universal TM $\ \mathcal{U}$ of Theorem 1.9 to ...
1
vote
0answers
11 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 ...
1
vote
0answers
84 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 $...
1
vote
1answer
79 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 ...
0
votes
0answers
68 views

Correctness proof: induction on sequence of steps, need a stronger claim?

Im trying to prove the correctness of the construction proposed in this site answer: a two stack PDA that simulates a Turing Machine. By "correctness" i mean to prove more or less formally that we can ...
1
vote
0answers
65 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)$ ...
2
votes
0answers
114 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 ...
0
votes
1answer
72 views

Why the universal Turing machine simulation in O(TlogT) cannot be applied to transform multi-taped Turing machine into single-taped?

Recently, I've read Hennie's Paper. I understood the construction of buffer zones, but why can't it be applied to yield a single-taped Turing machine?
1
vote
0answers
59 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 ...
1
vote
3answers
148 views

Is it 100% OK to say “All software doesn't need to know the system lower than the architecture level”?

Most of you know this diagram. If this diagram is true, all software is free to not know the levels lower than ISA. But it's not true. Softwares like performance-critical programs or system softwares ...
0
votes
2answers
286 views

Solving the Path Explosion Problem in Symbolic Execution

Looking at the Symbolic Execution limitations, there are some good solutions to the "Environment interactions" problems. However, the solutions to the path explosion problem are less than ideal. ...
1
vote
0answers
27 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:...
0
votes
0answers
36 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 ...
1
vote
0answers
18 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 ...
1
vote
0answers
46 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 ...
1
vote
2answers
51 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 ...
1
vote
0answers
58 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,...
2
votes
0answers
29 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 ...
1
vote
3answers
274 views

Minimal DFA with more states than its equivalent NFA

I understand that using a bad case for subset construction as provided through an example in the book - Introduction to Automata Theory, Languages and Computation, we can definitely have an NFA with $...
0
votes
0answers
71 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 ...
2
votes
2answers
465 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?
2
votes
0answers
98 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 ...
2
votes
1answer
1k views

Can every DFA be simulated by a PDA?

Given a Deterministic Finite Automata (DFA) $M_1$, does there always exist a Pushdown Automata (PDA) $M_2$ that accepts the same language as $M_1$? I.e. can any DFA be simulated by a PDA? ...
0
votes
1answer
126 views

CFG to PDA - no empty transitions

Working for my exam, this question popped up. Given the production rules below, draw a pushdown automaton to recognise the language it generates: S → AB A → BA B → BB B → T T → b ...
1
vote
1answer
158 views

Genetic Algorithm Getting Stuck on Certain Values

I'm attempting to teach myself something about genetic algorithms. I found a simple tutorial on it here, and it made enough sense that I was able implement the suggested example of generating a string ...
1
vote
0answers
427 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 ...
0
votes
0answers
43 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 ...
1
vote
1answer
108 views

Viable use of genetic algorithms to train neural nets in a poker bot?

  I am designing a bot to play Texas Hold'Em Poker on tables of up to ten players, and the design includes a few feed forward neural networks (FFNN). These neural nets each have 8 to 12 ...
1
vote
0answers
56 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 ...
3
votes
1answer
101 views

Equivalence of dfferent TM definitions

I stumbled upon these two defintions of a turing machine: http://www.cs.um.edu.mt/gordon.pace/Teaching/Complexity/CoursePage/Notes/chapter5.pdf http://scholar.harvard.edu/files/harrylewis/files/...
2
votes
1answer
321 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 ...
0
votes
0answers
65 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.
5
votes
1answer
999 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 ...
7
votes
2answers
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 ...
1
vote
0answers
32 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 ...
3
votes
1answer
138 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 ...
3
votes
1answer
278 views

An algorithm for comparing a DFA and a regular expression

Assuming I have an encoding of a DFA $<M>$ and a regular expression $<r>$, I'm interested in finding an algorithm for comparing whether or not $L(M)=L(r)$. I have thought about converting ...
5
votes
1answer
15k 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 ...
2
votes
1answer
152 views

Are there any LTL to _non_ deterministic Rabin automaton translators?

I know of two translators LTL -> deterministic Rabin automaton: Rabinizer3 ltl2dstar They produce deterministic automata, which can be much larger than their possible non-deterministic variants. Is ...
2
votes
0answers
29 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 ...
3
votes
1answer
56 views

Difference between large-scale optimization and equation-based simulation

Large scale optimization (for example using AMPL) can be used to solve equilibrium systems which have components with fixed mathematical relationships. What is the difference between this and using an ...
3
votes
1answer
296 views

Equivalent DPDA that always halts for every DPDA with empty stack language

I want to show that for every deterministic pushdown automaton with the language of the empty stack there is a deterministic pushdown automaton that always halts. my transition function of $P$ is $\...
1
vote
1answer
191 views

Is the simulation of how a warehouse functions (eg Amazon) a discrete event simulation problem

If i wanted to write a piece of software that simulated a warehouse where typical warehouse procedures occur eg loading of trucks onto conveyors goods being transported around a warehouse by ...
1
vote
2answers
296 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 ...
2
votes
2answers
898 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 ...
4
votes
1answer
262 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 ...
0
votes
0answers
383 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 ...