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.
176
questions
1
vote
0
answers
12
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 ...
-9
votes
1
answer
581
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
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
-8
votes
3
answers
494
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
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 ...
0
votes
1
answer
48
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 ...
- 161
1
vote
1
answer
49
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 ...
D.W.♦
- 152k
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 ...
D.W.♦
- 152k
1
vote
2
answers
36
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 ...
- 8,871
1
vote
1
answer
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 ...
- 38.3k
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 ...
1
vote
1
answer
151
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 ...
- 38.3k
1
vote
1
answer
204
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 ...
CommunityBot
- 1
0
votes
1
answer
71
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 ...
CommunityBot
- 1
0
votes
1
answer
54
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
19
votes
2
answers
4k
views
How can I convert the Turing machine the recognizes language $L$ into an unrestricted grammar?
According to this Wikipedia article, unrestricted grammars are equivalent to Turing machines. The article notes that I can convert any Turing machine into an unrestricted grammar, but it only shows ...
- 11
5
votes
1
answer
2k
views
Oblivious Universal Turing Machine in O(T log(T)) time
I'm currently reading Computational Complexity: A Modern Approach. In this book, they give a proof of a universal Turing machine $U$ such that if $M(x)$ runs in $T$ steps, then $U(\lfloor M \rfloor, x)...
- 21
2
votes
1
answer
233
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 ...
- 20.3k
5
votes
1
answer
2k
views
Why is simulation by non deterministic Turing machine faster than a deterministic one?
A deterministic universal Turing machine $U_D$ can simulate a deterministic turing machine $M_D$ in $O(T(n)log(T(n)))$ where $M_D$ runs in $O(T(n))$. But I came across an exercise in Sanjeev Arora and ...
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
5
votes
1
answer
1k
views
How to simulate a bidirectional TM on a regular one with time factor four?
In Computational Complexity A Modern Approach, one claim says that if $f$ is computable in time $T(n)$ by a bidirectional TM $M$, then it is computable in time $4T(n)$ by a unidirectional TM $\tilde{M}...
CommunityBot
- 1
2
votes
0
answers
41
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
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.4k
5
votes
2
answers
2k
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 ...
- 67
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
9
votes
1
answer
26k
views
Convert CFG to PDA
Is there any set of rules or methods to convert any context free grammar to a push down automata?
I already found some slides online but I wasn't able to understand them.
In slide 10 he speaks ...
- 29.1k
2
votes
0
answers
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 ...
- 21
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
0
votes
1
answer
244
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 ...
- 315
-1
votes
1
answer
32
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?
- 17.9k
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 ...
0
votes
2
answers
62
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 ...
- 3,443
0
votes
1
answer
896
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 ...
- 6,777
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
2
answers
120
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 ...
- 27.4k
0
votes
1
answer
42
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 ...
- 36
1
vote
0
answers
767
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,052
2
votes
1
answer
267
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 ...
- 4,358
4
votes
2
answers
1k
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 ...
- 151
0
votes
0
answers
83
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
1
vote
1
answer
318
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?
...
- 27.4k
0
votes
2
answers
198
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 ...
CommunityBot
- 1
2
votes
2
answers
122
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 ...
- 1,008
6
votes
3
answers
1k
views
Would creating a complete computer simulation of the human brain prove the Church-Turing thesis?
According to Wikipedia, the Church-Turing thesis "states that a function on the natural numbers is computable by a human being ignoring resource limitations if and only if it is computable by a Turing ...
0
votes
1
answer
150
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 ...
- 1,559
1
vote
1
answer
110
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 ...
- 51
0
votes
1
answer
435
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? ...
- 20.3k
-2
votes
2
answers
3k
views
Thompson's Construction Algorithm produces a different NFA
My teacher asked me to convert the regular expression $(a | b)^*$ to an NFA using Thompson's algorithm – well, I'm well aware of how this algorithm works, but since I'm not good at memorising details, ...
CommunityBot
- 1
3
votes
1
answer
204
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 ...
- 376
5
votes
2
answers
4k
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?
- 21