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
1answer
23 views

Are sample memory access traces/dumps available, and where?

I am looking for a realistic physical memory access trace/dump of significant, but not insane, length (on the order of 1M accesses) for the purpose of cache simulation. Preferably for a 16-bit or 32-...
0
votes
0answers
8 views

Is there complexity hierarchy of worlds/environments that are used for simulation or reinforcement learning in AI?

Is there complexity hierarchy of worlds/environments (i.e. state space * action space) that are used for simulation or reinforcement learning in AI? Hierarchy like ...
1
vote
1answer
32 views

A turing machine L takes a machine <M> which has to halt at for least n Inputs

I've been wondering about this problem for a while: Say we have L = { <M>, n | M has to halt for at least n Inputs} and multitapes are simulating various inputs bla bla How do I count how many ...
2
votes
1answer
49 views

Are Nondeterministic Finite Automata not allowed 'sink-states'?

By definition are Nondeterministic Finite Automata not allowed a 'sink-state' (non-accepting state we don't get out of)? I can see us having them for NFA but not necessary but do not see how they are ...
0
votes
0answers
6 views

Discrete Event Simulation: modeling entity arrivals

I have seen the stochastic introduction of simulated "entities" (typically queuing for service) via stochastic inter-arrival times. Specifically, the times between arrivals are simulated ...
0
votes
0answers
19 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 ...
2
votes
0answers
29 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 ...
-3
votes
1answer
41 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 ...
-6
votes
3answers
272 views

Does the Linz Ĥ applied to ⟨Ĥ⟩ correctly transition to its final reject state?

Does the Linz Ĥ applied to ⟨Ĥ⟩ correctly transition to its final reject state? This post requires reading the Linz proof at the end of this post first. Because ⊢* is defined to mean "an arbitrary ...
-5
votes
1answer
365 views

Could H correctly decide that P never halts?

Could H be adapted to correctly decide that P never halts? See also: The Halting problem proof is wrong? The standard pseudo-code halting problem template "proves" that the halting problem ...
0
votes
0answers
33 views

Simulating a multi-network environment in one device using Python

I am deploying a blockchain on a localhost where all nodes can communicate with each other using ports and APIs; however, a node/group of nodes can leave the main blockchain group. Some questions came ...
0
votes
0answers
14 views

Difficultly in understanding the construction corresponding how any Turing machine can be mimicked by an unrestricted grammar

I was going through the automata text by Peter Linz where I came across the construction below. To show the converse, we describe how any Turing machine can be mimicked by an unrestricted grammar. We ...
2
votes
0answers
59 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 ...
0
votes
0answers
47 views

What is the procedure for performing a binning analysis in Monte Carlo, or more generally, estimating autocorrelation times?

I'm working on a monte carlo project similar to the Ising model. I've found many examples on which I've based my code: https://github.com/danielsela42/MC_TBG_Model/blob/master/mc_project/mcproj_binned....
2
votes
0answers
35 views

What would you do if the author of a published CS article does not respond to code requests? [closed]

Since reproducibility is a major principle or basic norm of scientific experiments, simulations, and computations, what would you do or what to do if the author of a published CS article does not ...
2
votes
0answers
40 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 ...
0
votes
1answer
174 views

Is NP in NP/Poly?

The answer is yes, NP/poly is defined as the class of problems solvable in polynomial time by a non-deterministic Turing machine that has access to a polynomial-bounded advice function--the advice ...
-1
votes
1answer
24 views

single circuit simulating multiple Turing machines

You can simulate polynomial time Turing machines with polynomial size circuits, can you simulate multiple poly time TMs with a single poly size circuit?
0
votes
1answer
68 views

Is there any hope for real "simulated machines" in our lifetime?

Without going into details about my life's story, here's the basic facts: I grew up with 386 and 486 and Pentium PCs running MS-DOS 5 (I believe), Windows 3.1 and Windows 95, a well as various game ...
1
vote
0answers
52 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 ...
0
votes
2answers
52 views

Are objects appropriate for modeling the real world?

First of all, I know objects are not meant to model the real world, although they have been marketed as such and perhaps that was an intention at some point. Here I say 'modeling the real world' in a ...
0
votes
1answer
406 views

What is the difference between a simulator, emulator, and cross compiler?

As far as I understand, cross compilers, emulators, and simulators are all ways that one computer system to be able to behave like or run another computer system. What is the difference between these ...
0
votes
0answers
59 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 ...
0
votes
2answers
104 views

What subfields in computer sciences may one study without learning Object Oriented Programming?

What subfields in computer sciences may one study without learning Object Oriented Programming or is there some kind of degree in Computer Science without the OOP knowledge requirement? Is there a ...
0
votes
1answer
28 views

Encoding huge number of tape-symbols of a turing machine in the simulation of the turing-machine using real computer

I was going through the classic text "Introduction to Automata Theory, Languages and Computation" by Hopcroft,Ullman,Motwani where I came across the simulation of a turing machine using a real ...
1
vote
0answers
462 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 ...
0
votes
0answers
51 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. ...
1
vote
1answer
243 views

Priority Queue Using Stack

Can one build a priority queue using stacks, such that the priority queue has the same complexity for each operation. Could it be done? If so how? If not what is the best solution that can be done? ...
0
votes
2answers
189 views

Does the callback concept of programming have any basis in computer science?

Although I seriously code with computer languages in general since 2010 and as an amateur programmer with programming languages in particular since 2015 (primarily Bash and JavaScript imperative ...
2
votes
2answers
92 views

Does the pigeonhole principle rule out the possibility of losslessly simulating a universe the size of our own?

Say you had a very powerful computer and wanted to run a completely lossless simulation of a universe approximately the same size as our own: $10^{80}$ particles. Each particle in the simulation has ...
0
votes
1answer
112 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 ...
2
votes
1answer
163 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 ...
1
vote
1answer
62 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 ...
0
votes
1answer
221 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? ...
3
votes
1answer
183 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
100 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
21 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
121 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$ ...
1
vote
1answer
792 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 ...
1
vote
0answers
180 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
781 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 ...
1
vote
1answer
105 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
65 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
281 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
861 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
31 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
66 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
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 ...
1
vote
0answers
102 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
78 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 ...