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

35 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
130 views

### Make a tag system simulate a finite automaton?

Tag systems are Turing-complete. I was wondering if there is any easy way to create tag systems that simulate finite automata. So create tag systems that recognize languages, e.g. by having at the end ...
1k views

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 ...
249 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 ...
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 ...
103 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 ...
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 ...
208 views

50 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 ...
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 ...
45 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 ...
68 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.
433 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 ...