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.

178 questions
Filter by
Sorted by
Tagged with
1 vote
35 views

Complexity of simulations in simulations

This video of a group, who simulated (a very simple version of) Minecraft inside Minecraft itself got me thinking about the performance of such setups. Another example to what I'm referring to, would ...
59 views

State Machines as Functors

I'm looking for more examples of the following model of state machines: in David Spivak's book on category theory, he gives in section 3.1.2.10 and in application 4.3.1.9, a description of a finite ...
1 vote
17 views

definition of P-samplable distribution that allows non-binary fractions

Arora and Barak (in chapter 18, on average-case complexity) define a polynomial-time samplable (or P-samplable) distribution $D$ (actually a family $\{D_n\}$, for each output length $n$) as having an ...
1 vote
27 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
98 views

What is the most efficient way to represent an directed dynamic massive 3D graph?

I know that there are many techniques to represent graphs. Suppose I have a directed massive 3D graph with 100,000 nodes at maximum. Suppose the graph looks somewhat like the following: Suppose each ...
• 153
1 vote
76 views

How to simulate a Discrete Event Simulation model with a real-time server?

My Problem is having to work with real-time server in a DES model. I have the following situation: I want to build a discrete event simulation model (Using event scheduling world view). However, this ...
• 113
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 ...
• 213
1 vote
41 views

Can all non-quantum physical systems be efficiently simulated on a classical computer?

Is it true that simulating classical physical systems is in P, i.e. can be done efficiently on Turing machines or are there known exceptions? I'm thinking of chaotic systems but I'm also curious more ...
• 141
38 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 ...
1 vote
167 views

Prove the equivalence of the modified Turing Machines and the standard Turing Machines

We have a Turing Machine that cannot write the same symbol it has read in a transition, meaning it should always alter the symbol when passing it. How can we prove that such machines have equal ...
79 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-...
• 111
1 vote
254 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 ...
305 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 ...
27 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
46 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
94 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 ...
506 views

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

Applying a Simulating Halt Decider to the Linz Halting Problem Proof A simulating (at least partial) halt decider correctly predicts whether or not its correctly simulated input can possibly reach its ...
• 87
606 views

Are the halting problem proofs refuted by software engineering?

Can D simulated by H terminate normally? The x86utm operating system based on an open source x86 emulator. This system enables one C function to execute another C function in debug step mode. When H ...
• 87
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
36 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 ...
• 21
45 views

• 237
1 vote
1k 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 ...
• 13
1 vote
241 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
918 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
1 vote
122 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
67 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