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
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 ...
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 ...
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 ...
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. ...
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 ...
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)? ...
1
vote
1answer
2k 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 ...
4
votes
1answer
308 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 ...
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 ...
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 ...
14
votes
4answers
767 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 ...
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 ...
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 ...
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 ...
3
votes
3answers
731 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 ...
6
votes
3answers
930 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 ...
5
votes
1answer
368 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
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 ...
4
votes
1answer
737 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}...
2
votes
1answer
3k views

Converting final state PDA to empty stack PDA

I'm having a problem understanding this conversion. Let's say we have a CFL like this: $ { a^nb^m : n > m } $ A final state acceptance PDA for this language would push $A$ symbols in the stack for ...
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. ...
4
votes
1answer
265 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} \...
2
votes
1answer
368 views

Space requirement of a universal Turing machine

Given a representation $g$ (e.g. the Gödel number) of a Turing machine $B$, a universal Turing machine $A$ can simulate $B$. If $B$ is restricted to using at most $n$ memory cells of its tape and the ...
2
votes
0answers
199 views

Context free grammar as minimal solution of a system of equations

It is a well-known fact that language generated by a context-free grammar is the minimal solution of a particular system of equations, for example: $$\begin{align*} X &=\{{\epsilon}\} \cup Y\\ X ...
2
votes
2answers
333 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 ...
1
vote
2answers
316 views

Variant of Turing machine

How to prove that standard Turing machine is equivalent to a variant model where a string is accepted if the machine enters an accept state during computation? However, the machine may leave the ...
1
vote
2answers
54 views

How to prove a side effect in a function

I asked a question earlier about Saving to the Database, which was very general and about the requirements for a proof when you go through many layers of non-verified systems such as the network and ...