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
8 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
14 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
38 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 ...
0
votes
0answers
18 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 ...
2
votes
0answers
32 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
79 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
133 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
737 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
96 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
64 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
14 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
79 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
56 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
118 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 ...
0
votes
0answers
14 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 ...
-1
votes
1answer
43 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
35 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
552 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
226 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
245 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
62 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
276 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
174 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
4k 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 ...
3
votes
1answer
260 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
128 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
100 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
101 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. ...
1
vote
0answers
150 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
94 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 ...
2
votes
1answer
91 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 ...
2
votes
0answers
150 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 ...
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
276 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
530 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 ...
5
votes
1answer
180 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
176 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
30 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 ...
1
vote
2answers
402 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
43 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
63 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 ...