Questions about simulating one model in another. This includes simulating reality in any model, or simulating a machine model with Turing machines.
9
votes
2answers
132 views
What randomness really is
I'm a Computer Science student and am currently enrolled in System Simulation & Modelling course. It involves dealing with everyday systems around us and simulating them in different scenarios by ...
5
votes
1answer
50 views
1/r attractive force by cellular automaton
Does there exist a cellular automaton (in 2D) which simulates a $1/r$ force between particles?
More specifically, I would like to know whether it is possible, with strictly local update rules, to ...
0
votes
0answers
18 views
Simulation of a model
I am not sure if this is an appropriate place to ask, since the question may be related to software engineering.
In embedded control domain, model-driven engineering allows a design model to be ...
5
votes
1answer
49 views
Time Complexity of Universal Turing Machine Simulations and the Time Hierarchy Theorem
I have a little problem to understand the proof of the Time Hierarchy Theorem (Hennie and Stearns, 1966) that ensures the existence of a language acceptable in $U(n)$ but not acceptable in $T(n)$ for ...
0
votes
1answer
66 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 ...
-1
votes
1answer
42 views
Circuit Maker repalcement [closed]
I'm studying CS, and we have a course called "computer systems architecture" which is merger of two former "logic systems theory" and "mips asm" courses (I hope my translations are correct).
We have ...
0
votes
0answers
65 views
What is the easiest programming language to simulate a computer architecture? [closed]
What is the simplest computer language I can use to simulate a SIMD multiprocessor system if the # of processing elements, # of memory units, and an interconnection network is specified?
The ...
6
votes
1answer
104 views
Simulate the concatenation of two log-space programs in log-space
I've got two log-space programs $F$ and $G$.
Program $F$ will get input in array $A[1..n]$ and will create the output array $B[1..n]$.
Program $G$ will get as input $B$ as created by $F$ and create ...
5
votes
1answer
234 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 ...
3
votes
2answers
103 views
Robustness of Turing Machines - 3 dimensional case
How can one show that a machine with a three dimensional memory arranged in an infinite grid can be simulated by a single-tape Turing machine? I'd imagine there's some sort of mapping possible from ...
0
votes
1answer
52 views
To prove Turing-completeness, is it enough to prove capability of producing arbitrary output?
Turing completness is being typically proved via reduction to already proved Turing-complete machine.
Can the same be obtained by showing, that the machine in question is capable of generating ...
1
vote
1answer
154 views
Multitape Turing machines against single tape Turing machines
Introduction: I recently learned that a multi-tape Turing Machine $\text{TM}_k$ is no more "powerful" than a single tape Turing machine $\text{TM}$. The proof that $\text{TM}_k \equiv \text{TM}$ is ...
4
votes
1answer
61 views
Who conceived the concept of Discrete Event Simulation, and when?
I'm trying to trace back the origin of the general concept of Discrete Event Simulation and found a 1968 article by Fishman and Kiviat mentioning the term. It is titled The statistics of ...
3
votes
1answer
472 views
First-Come-First-Serve scheduling algorithm - what happens to process after returning from I/O? where does it go in the queue
There are three processes in line
P0, P1, P2
1) P0 registered and executes
2) P0 I/O blocked
3) so P1 executes
4) P1 I/O blocked
5) P0 executes. ??
After P1 must come P2 that is what FCFS ...
3
votes
1answer
85 views
Could I simulate the implementation of memory components
I am currently reading the IEEE paper A Memory-Efficient Parallel String Matching
Architecture for High-Speed Intrusion Detection by Kai Zheng, Bin Liu, Xin Zhang, and Yunhao Liu.
In the paper ...
5
votes
2answers
238 views
Infinite alphabet Turing Machine
Is a Turing Machine that is allowed to read and write symbols from an infinite alphabet more powerful than a regular TM (that is the only difference, the machine still has a finite number of states)?
...
3
votes
1answer
213 views
How does a single-track Turing machine simulate a multi-track Turing machine?
It's easy to see how a multi-track Turing machine can simulate a single-track Turing machine; it does so by ignoring all but the first track. But how does it work the other way? I need a specification ...
4
votes
1answer
128 views
On-line simulation of a two-head tape Turing machine using single-head tape(s)
I have a question and I haven't been able to figure out the answer yet. I need to do the on-line simulation of a two-head tape Turing machine using single-head tape(s). I've found some online articles ...
12
votes
4answers
411 views
Is every linear-time algorithm a streaming algorithm?
Over at this question about inversion counting, I found a paper that proves a lower bound on space complexity for all (exact) streaming algorithms. I have claimed that this bound extends to all linear ...
3
votes
0answers
99 views
For the time hierarchy theorem, how is the input translated efficiently?
I'm trying to understand the proof of the time hierarchy theorem appearing in sipser's book. The proof requires a TM M to simulate an arbitrary TM N without too much slowdown. In particular, it is ...
8
votes
1answer
180 views
Universal simulation of Turing machines
Let $f$ be a fixed time-constructable function.
The classical universal simulation result for TMs (Hennie and Stearns, 1966) states that there is a two-tape TM $U$ such that given
the description ...
8
votes
1answer
163 views
Prove that a boolean function computable in T(n) by a RAM machine is in DTIME(T(n)^2)
The question is exercise 1.9 from Arora-Barak's book Computational Complexity — A Modern Approach:
Define a RAM Turing machine to be a Turing machine that has random access memory. We formalize ...
