Questions about simulating one model in another. This includes simulating reality in any model, or simulating a machine model with Turing machines.

learn more… | top users | synonyms

3
votes
1answer
28 views

Converting generalized NFAs to NFAs

I came across generalized nondeterministic finite automata (GNFAs) in Sipser's Introduction to the Theory of Computation. These are automata where transitions are labelled with regular expressions, ...
0
votes
1answer
37 views

Connection of “modern” runtimes and number of steps on a Turing machine

Why an evaluation of Turing machine efficiency is equal to the algorithm which is implemented by this machine and vise versa? For example, we can say that efficiency of merge sorting algorithm is ...
2
votes
1answer
70 views

Proof technique in complexity theory

I have a (stupid ?) question about complexity theory. It's about a "proof technique". I want to compare 2 models of computation. I want to prove that for each langage recognized in polynomial time by ...
1
vote
0answers
37 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 ...
1
vote
1answer
47 views

Convert DFA to Regular Expression

In this old exam-task I don't understand all the steps to convert the DFA below to a Regular Expression. The q_2 state is eliminated first. The provided solution to eliminate q2 is: ...
2
votes
0answers
76 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 ...
4
votes
3answers
385 views

Rice's theorem vs Turing completeness

I would like to clarify this because I see some kind of contradiction between Rice's theorem and Turing completeness. This is the problem: In building an Universal Turing Machine to emulate another ...
4
votes
1answer
72 views

Relation between RAM and Turing machine

Denote $D$ a set of finite sequences of integers. In Papadimitriou's "Computational Complexity" in theorem 2.5 it is proved that if a RAM program $\Pi$ computes a function $\phi$ from $D$ to integers ...
1
vote
2answers
137 views

If a DFA can be simulated by a real program, can it be simulated by a TM

In proofs of decidability, we often want to simulate another model of computation by a Turing machine. But if I can simulate a $\mathsf{DFA}$ by, say, a C program, then is there some result which says ...
0
votes
0answers
24 views

Name for a Type of Simulation

I have come up with a type of simulation "game" but I cannot find anything describing it online. The simulation has a 2D "world" with a number of automatons on a discrete grid, similar to the game ...
0
votes
2answers
80 views

How many states when converting CFG to PDA

When converting a CFG to a PDA I know that you get three main states, Qstart, Qloop and Qaccept. But Qloops will need a various amount of states, and my question is how many? Is there a way to find ...
1
vote
0answers
25 views

simulation of Randomized distributed algorithms [closed]

I want to implement various Randomized Distributed algorithms for MIS, Broadcast, Coloring in Radio Networks. I want use very high level language or any simulator for this. Please suggest on this.
1
vote
0answers
27 views

fraction of volume of a rectilinear grid cell within some radius of the origin [closed]

I have a sphere (radius R) on a rectilinear grid. Some cells intersect the edge of that sphere, call them 'edge cells'. Designate a given cell by indices [i,j,k] which refer to the lowest-index vertex ...
2
votes
0answers
278 views

Difference between deterministic and nondeterministic universal turing machine

It is known that a nondeterministic universal turing machine (UTM) can simulate another nondeterministic TM with running time $t(n)$ in time $c t(n)$, where $c$ is a constant. It is also known that a ...
1
vote
2answers
100 views

Prove Queue Automaton is equivalent to Turing Machine

A deterministic queue automaton (DQA) is like a PDA except the stack is replaced by a queue. A queue is a tape allowing symbols to be written (push) on the left-end and read (pull) on the right-end. ...
3
votes
1answer
130 views

How to convert a Turing Machine program to a tiling using Wang Tiles?

This is a cross-post from a post on MathSE due to lack of answers. To illustrate my question I provide the following example. The website Online Turing Machine provides a Turing Machine simulator. ...
1
vote
1answer
91 views

Simulating a TM with a 2-head, right moving TM

Is it possible to simulate a regular Turing Machine with a TM with the following specs? There are two heads, one of which can read, one of which can write Both heads can only move right When a head ...
0
votes
1answer
147 views

Right moving turing machine

I am interested in simulating any turing machine with a turing machine that is allowed only to move right. I guess that it should be pretty standard material and likely it is trivial (or known to be ...
1
vote
2answers
268 views

Convert a non-deterministic Turing machine into a deterministic Turing machine

How can we systematically convert a non-deterministic Turing machine into a deterministic Turing machine that recognizes the same language?
1
vote
1answer
430 views

Two Dimensional Tape of Turing Machine

I was looking at this: http://www.cs.odu.edu/~toida/nerzic/390teched/tm/othertms.html At the very beginning, they show a 2d tape and (I assume) it's 1d equivalent. However, I cannot figure out they ...
0
votes
1answer
1k views

Show how to k tapes of Turing machines into one dimensional Turing machine

I'm reading Sipser and I'm finding it hard to understand what the process is such that if you give me k Turing machines with k tapes, I can spit out an equivalent Turing machine with only one tape. An ...
5
votes
0answers
72 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 ...
0
votes
2answers
506 views

How can a Turing Machine recognize a regular language?

This is a practice problem for a midterm in a class I'm taking: Given a regular language $L$, describe formally a Turing machine that recognize $L$. I'm not sure how I should do that.
1
vote
1answer
132 views

Why is software emulation of alternative architectures so hard/slow?

I recall hearing briefly about this back in one of my CS courses on hardware, but I can't recall many of the details, nor can I find anything online that talks about it. A search on Google only yields ...
2
votes
1answer
192 views

Is it impossible to truly emulate a system if its actual clock speed is the same?

As I understand emulation a rule of the thumb says that a computer must be around a order of magnitude more powerful to emulate another system without resorting to tricks. This is because for every ...
15
votes
8answers
758 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 ...
9
votes
2answers
151 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 ...
5
votes
1answer
450 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
2k 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 ...
6
votes
1answer
134 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 ...
7
votes
1answer
452 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
161 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
65 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
459 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 ...
5
votes
1answer
90 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
122 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
470 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)? ...
4
votes
1answer
430 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
212 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
489 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
147 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 ...
9
votes
1answer
302 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 ...
10
votes
1answer
242 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 ...