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

2
votes
0answers
24 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)...
0
votes
1answer
36 views

Is it always possible to convert a k-tape Turing machine to a single-tape one without increasing its running time complexity exponentially?

I am studying the past exam paper of course Theory of Computation. I know it is always possible to convert a k-tape Turing machine to a single-tape one, but how will the running time complexity be ...
-1
votes
0answers
14 views

relation of weak bisimulation

I've two separated processes P and Q. P evolves this way: loop forever p1: not-critical p2: await-turn=1 p3: critical-section p4: turn<-2 Q: <...
-1
votes
0answers
62 views

Every PDA can be shown to be equivalent with a PDA with two different stack symbols

Is statement from title true? If yes how to prove it? I mean how to prove that every PDA with stack alphabet of multiple symbols can be reduced to PDA with stack alphabet with only two symbols. I know ...
2
votes
1answer
77 views

Turing Machine with additional finite memory of size $n$

The question itself: Let us define a generalization of Turing Machines to include a finite memory of >size $n$. We denote such a Turing Machine formally as: $M_{mem} = (Q, Σ, γ, δ_{...
3
votes
0answers
55 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 ...
8
votes
1answer
70 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 ...
0
votes
0answers
20 views

Particle locating/collision prediction in bounded (two-dimensional) environments

I believe that many physics engines, particle simulators, and even video games use discrete-event simulation to determine where a particle or object is at any moment, and the direction in which it is ...
4
votes
1answer
40 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}^{+...
0
votes
0answers
20 views

Stepping through a sequence of grouped logic gates

I'm performing a simulation of protein-protein interactions. I'm using Python to code logic gates as functions to model protein interactions. My model is basically a series of groups (...
-3
votes
1answer
16 views

Equivalence of DFA' definitions

According to wikipedia DFA accepts word $w$ by one of two definitions: A word $w$ is accepted by $M$ if $\hat\delta(q_0,w)\in F$. A word $w=w_1w_2\dots w_n$ is accepted by $M$ if $\exists r_0,\dots,...
2
votes
0answers
38 views

Proving weak simulation

I want to prove something but I am not sure if it is the right way to do it. I have two LTS that define different semantics. A=($Q_a,Λ,\to)$, and B=$(Q_b,Λ\cup\{\beta\},\leadsto)$, where $\beta$ is ...
2
votes
1answer
82 views

Quantum computer simulators with proper measurements

I have been looking for quantum computer simulators and came across QCAD (http://qcad.osdn.jp/). It is stated on their website that "Measurement gates on QCAD are different from real measurements." ...
4
votes
1answer
164 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 ...
3
votes
3answers
748 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 ...
2
votes
1answer
111 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 ...
1
vote
1answer
66 views

Why is universal turing machine considered with only one head?

While defining the following time hierarchy theorem (for deterministic case ) : If $f(n)\log{f(n)}=o(g(n))$ then there are languages decidable in $O(g(n))$ which cannot be decided in $O(f(n))$ ...
0
votes
0answers
17 views

How BDI agent can select next step (action)?

I am reading now about BDI (Belief-Desire-Intention) agents. I guess that this type of agents is the most popular model of cognitive agents and agents of multi-agent systems. Of course I am reading ...
-2
votes
1answer
103 views

Every non deterministic Turing machine has an equivalent deterministic Turing machine Formal proof [closed]

is there exist a formal proof for Equivalence of deterministic and non deterministic Turing Machine ? i read Martin Davis and Sipser's book and there is no formal proof
2
votes
2answers
72 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 ...
2
votes
1answer
126 views

Polynomial hierarchy: inclusion between spaces

Using the definition for the polynomial hierarchy: $$ \Sigma_{i+1}^P = NP^{\Sigma_i^P} $$ $$ \Pi_{i+1}^P = coNP^{\Sigma_i^P} $$ I have been asked to to show that: $$ P^{\Pi_k^P } \subseteq \Pi_{k+1}...
0
votes
0answers
15 views

Simulation Relation Between Two Büchi Automata

Suppose you have two Büchi Automata: $A=(Q_A,\Sigma,I_A,\delta_A,F_A)$ $B=(Q_B,\Sigma,I_B,\delta_B,F_B)$ where: $Q_A$ and $Q_B$ are finite sets of states $\Sigma$ is the input alphabet $I_A\...
-1
votes
1answer
48 views

How would a finite state transducer with no output function work?

Say I have a finite state transducer, 6 tuple FST with a set of states, input symbols, output symbols, transition function, a start state, and an output function. If I combine the output function into ...
2
votes
0answers
41 views

Expressing classic automata in modern terms

This semester I was introduced to finite automata (FSM), then pushdown automata (PDA), and now the Turing machine (TM). Granted that there're many possible implementations of these abstractions (...
4
votes
1answer
48 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 ...
1
vote
1answer
39 views

Simulating continuous time semi-Markov state machine and changing transition probability on the fly

The problem that I'm trying to solve (well, I think that I almost did, but need a review from someone more experienced) is about changing probability of the transition for semi-Markov state machine ...
1
vote
1answer
687 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 ...
14
votes
5answers
4k views

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

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 ...
4
votes
1answer
260 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 ...
-1
votes
1answer
391 views

Converting this NFA to Turing Machine

I'm asked to choose a DFA and convert it to NFA and then convert it to Turing machine... I have done the first two parts as follows: DFA: --> NFA: --> Turing machine: ??? I haven't found ...
1
vote
1answer
63 views

Standard problem sets for metaheuristics

I'm wanting to dabble with metaheuristics and am interested to know what the "hello world" problem sets are. In other words, what are the common problems (e.g Traveling Salesman, Vehicle Routing ...
0
votes
1answer
60 views

Simulating a combinatorial network [closed]

I have various Boolean functions in the sum of products format. I "convert" these via combinatorial logic synthesis into a combinatorial network as an And-Inverter Graph - therefore this network only ...
8
votes
1answer
295 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 ...
2
votes
3answers
184 views

Can any recursion implementation be written as tail-recursion?

Can any method that uses recursion be written as tail-recursion?
0
votes
1answer
36 views

How do I manage flow control with no ELSE statement? (on Turing machine)

I have been given the problem of writing a turing machine with the commands: if, while, whileNot, read X, write X, goLeft, goRight, HALT The problem was simply "...
8
votes
3answers
5k 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 ...
4
votes
1answer
98 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
68 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} \...
3
votes
1answer
292 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. ...
-1
votes
1answer
130 views

Proving equivelance of a multijump turing machine and a turing machine

I'm having trouble getting started on this proof, and I was hoping you guys could give me a couple hints/point me in the direction of where to start? Here's the problem: Consider a multijump Turing ...
0
votes
1answer
115 views

Simulate a regular Turing Machine with one that cannot write blanks

Consider a Turing machine that cannot write blanks. How does one show that such a machine can simulate a standard Turing machine?
1
vote
0answers
27 views

How to make logical inference from simulated data

I have data collected from a computer simulation of football games which seem to have recurring patterns of the following form. if madrid plays arsernal and the match ends under 3 goal, then on ...
2
votes
1answer
103 views

Computational equivalences between a calculus and an automaton model

This Wikipedia table (template for "Formal languages and grammars") maps grammar to language to abstract machine for more than a dozen languages. http://en.wikipedia.org/wiki/Template:...
1
vote
0answers
159 views

K -> 2 tape reduction for nondeterministic Turing machines

How to I show that any language in NTIME(T(n)) can be accepted by a non-deterministic 2-tape O(T(n)) time-bounded Turing machine, with modifiable input tape? I've seen the k to 2 tape reduction for ...
3
votes
1answer
97 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
63 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 O(...
2
votes
1answer
92 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 ...
3
votes
0answers
156 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}...
5
votes
2answers
6k 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 ...
2
votes
0answers
303 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 ...