# 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.

145 questions
Filter by
Sorted by
Tagged with
38 views

### Prof Knuth's MIX computer - Card Reader and illegal characters

I'm reading through Knuth's "The Art of Computer Programming" volume 1 (3rd edition), with the goal of understanding the complete workings of his hypothetical MIX computer in order to implement MIX in ...
38 views

### Why can’t you simulate a Turing machine with a one-stack PDA by messing with the stack?

I have heard that a matrix can be modeled as just an one array by declaring increasingly large spaces to be from the second array, and that the least you need for a Turing machine is just a PDA with ...
24 views

### Simulations between Turing machines

I've got a question. How can i simulate Turing machine with a double-sided infinite tape by a Turing machine with one-sided infinite tape? The condition is, that the simulation of one step of the ...
13 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 ...
49 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? ...
74 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 ...
33 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 ...
13 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 ...
93 views

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 ...
683 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?
101 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 ...
2k 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? ...
140 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 ...
167 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 ...
461 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 ...
44 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 ...
112 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 ...
58 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 ...
107 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/...
358 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 ...
66 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.
1k 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 ...
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 ...
33 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 ...
158 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 ...
308 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 ...
17k 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 ...
159 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 ...
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 ...
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 ...
331 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 \$\...