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.

Filter by
Sorted by
Tagged with
22
votes
3answers
4k views

How to show two models of computation are equivalent?

I'm seeking explanation on how one could prove that two models of computation are equivalent. I have been reading books on the subject except that equivalence proofs are omitted. I have a basic idea ...
19
votes
1answer
3k 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 ...
18
votes
5answers
6k views

Why is a quantum computer not capable of solving more problems than a classical computer? [duplicate]

On the Wikipedia page for quantum algorithm I read that [a]ll problems which can be solved on a quantum computer can be solved on a classical computer. In particular, problems which are undecidable ...
16
votes
1answer
1k 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 of ...
14
votes
4answers
784 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 ...
12
votes
3answers
22k views

How to create DFA from regular expression without using NFA?

Objective is to create DFA from a regular expression and using "Regular exp>NFA>DFA conversion" is not an option. How should one go about doing that? I asked this question to our professor but he ...
11
votes
1answer
17k views

How to map the tapes of a “k-tape” Turing Machine into the single tape of a “1-tape” 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 ...
11
votes
2answers
314 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 ...
10
votes
1answer
1k views

How can a universal Turing machine simulate “bigger” ones?

I'm trying to find the answers of two questions about the Universal Turing machine. How can the Universal Turing machine simulate a Turing machine if the one that is being simulated has a bigger ...
10
votes
1answer
602 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 this ...
9
votes
2answers
3k 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)? ...
9
votes
3answers
3k views

Why use $\mu$-calculus and not LTL,CTL,CTL*?

It is known that the temporal logics LTL,CTL,CTL* can be translated/embedded into the $\mu$-calculus. In other words, the (modal) $\mu$-calculus subsumes these logics, (i.e. it is more expressive.) ...
9
votes
1answer
22k 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 ...
8
votes
1answer
2k 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 ...
8
votes
1answer
159 views

Church-Turing and physical PDEs

When I read about the Church-Turing thesis it seems to be a common claim that "physical reality is Turing-computable." What is the basis for this claim? Are there any theoretical results along these ...
7
votes
2answers
1k views

Does there exist an equivalent arithmetic circuit for each computable function?

Does there exist an equivalent arithmetic circuit for each computable function? I've been trying to wrap my head around the statement above, but haven't found a counter example although I believe ...
7
votes
1answer
221 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
0answers
128 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 ...
6
votes
3answers
931 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 ...
6
votes
3answers
25k 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 $q_2$ is: If we first ...
6
votes
1answer
483 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 ...
5
votes
1answer
1k 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 ...
5
votes
1answer
179 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 discrete-...
5
votes
1answer
18k views

Steps to convert regular expressions directly to regular grammars and vice versa

I came across following intuitive rules to convert basic/minimal regular expressions directly to regular grammar (RLG for Right Linear Grammars, LLG for Left Linear Grammars): Then I came across many ...
5
votes
1answer
1k views

Brzozowski algebraic method for NFA

Currently I have a graph (basically, a state graph) in Scala which is similar to an NFA some nodes have multiple in/outgoing edges single start state there might be multiple final states a state can ...
5
votes
1answer
116 views

How would I simulate a network to explore the percolation threshold of a network connected by the knight's move?

"If we consider the squares of an infinite chess board as nodes of our graph and consider each to be connected to the other eight squares that are a knight's move away from it what is the percolation ...
5
votes
1answer
1k views

pda: transformation between acceptance by empty stack and final states

I am stuck with understanding the transformation of final-state acceptance automaton into empty-stack acceptance automaton. From everywhere that I've read, it always says introduce a new start state ...
5
votes
1answer
46 views

Can we always reduce the weights of a weighted graph to rationals and preserve equality relationships?

Let $G = (Q, \Delta, W)$ be a finite weighted graph with $\Delta: Q \times Q$ and $W: Q \times Q \to \mathbb{R}^{+}$. Is it the case that there always exist a function $W': Q \times Q \to \mathbb{Q}^{+...
5
votes
3answers
2k views

Can any recursion implementation be written as tail-recursion?

Can any method that uses recursion be written as tail-recursion?
5
votes
1answer
1k 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. ...
5
votes
1answer
373 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 ...
4
votes
1answer
3k 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
2answers
215 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 ...
4
votes
1answer
1k 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 ...
4
votes
2answers
813 views

Efficient simulation of an NFA, while preserving the paths to the accept states

The standard way of simulating an NFA on a computer (for implementing regex engines etc) is to construct a DFA that accepts the same language. Otherwise you get problems like exponential blowup. ...
4
votes
1answer
313 views

Proof that PDA's with different definitions have same expressive power

Let $P$ be a push down automaton $(Q,\Sigma,\Gamma,\delta,q_s,F)$, where $Q$ is the set of states, $\Sigma$ is the input alphabet $\Gamma$ is the stack alphabet $\delta$ is the transition function ...
4
votes
1answer
2k 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
2answers
2k views

DFA to regular expression how to deal with 'sink state'

Didn't find a clear statement on this so I just want to make sure I'm right. If I have DFA with edges leading to a 'sink state' (non-accepting state we don't get out of) the edges leading to the sink ...
4
votes
1answer
269 views

Simulate NPDAs with DTMs using only polynomial overhead

We know by polynomial-time parsing algorithms like the classical CYK algorithm that $\mathrm{CFL} \subseteq \mathrm{P}$. Furthermore, it is easy to show by direct simulation that $\mathrm{DCFL} \...
4
votes
1answer
1k 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 ...
4
votes
1answer
99 views

Research work on computational models for a “specific” person's behaviors

Is there active research work on creating computational models of a "specific" person's behaviors (general behaviors, emotions, actions...)? What are some references for such research? I tried google ...
4
votes
0answers
1k 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)...
4
votes
1answer
742 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}...
4
votes
0answers
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 ...
3
votes
3answers
734 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 ...
3
votes
1answer
716 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 ...
3
votes
2answers
530 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 ...
3
votes
2answers
237 views

What is a program in self-replicating programs?

I'm trying to understand the workings of artificial life as exemplified by systems like Tierra or Avida. The idea behind these systems is that organisms are modeled as assembly-language programs that ...
3
votes
2answers
5k 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
108 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 ...