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

1
vote
1answer
34 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 ...
11
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
37 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
50 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
53 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
52 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 ...
6
votes
1answer
102 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
107 views

Can any recursion implementation be written as tail-recursion?

Can any method that uses recursion be written as tail-recursion?
0
votes
1answer
33 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 ...
6
votes
3answers
314 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 ...
1
vote
0answers
26 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 ...
2
votes
0answers
27 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
161 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
121 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
66 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
23 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 ...
0
votes
0answers
44 views

Simulating two dimensional tape TM with ordinary two tape TM

So I know that any multiple tape Turing Machine can be simulated with the one tape TM. But what about if we have a two dimensional tape TM? Can it be simulated with the ordinary two tape TM? Will they ...
2
votes
1answer
99 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
108 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
66 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
52 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
88 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
103 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 ...
4
votes
2answers
3k 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
188 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
493 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
130 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
161 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
28 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
263 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
32 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
52 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
611 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
685 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
366 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
141 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 ...
1
vote
1answer
369 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 ...
0
votes
1answer
102 views

Techniques (tools) to convert temporal logic (CTL,CTL* or LTL) to μ-calculus formulae

Suppose one wants to use a μ-calculus model checker, but specify things in temporal logics, which is easier (more intuitive). Is there a technique (even better, a tool) that automatically translates ...
2
votes
2answers
650 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?
7
votes
3answers
778 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.) ...
1
vote
1answer
1k 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
4k 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
87 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
1k 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
140 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 ...
3
votes
1answer
374 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 ...
9
votes
2answers
188 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 ...
3
votes
1answer
129 views

How to eliminate for/if/while from algorithms when it's possible

Is there any way to find out how to replace for/if for elementary recursive algorithms? I know that primitive recursive functions cannot basically eliminate "for", but for elementary recursive ...
5
votes
1answer
691 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
4k 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 ...