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.

186 questions
25
votes
3 answers

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 about what it means for two models of computation…
Mrk
  • 3,758
  • 26
  • 35
19
votes
2 answers

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 how to convert a grammar to a Turing machine. How…
Ava Petrofsky
  • 375
  • 2
  • 5
18
votes
5 answers

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 undecidable using classical computers remain undecidable using…
user2609980
  • 305
  • 2
  • 6
18
votes
1 answer

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 a TM $\langle M \rangle$ , and an input string $x$…
Kaveh
  • 22,767
  • 4
  • 56
  • 113
15
votes
4 answers

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 time algorithms. This is a bit bold as in…
Raphael
  • 73,461
  • 31
  • 185
  • 415
15
votes
1 answer

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 example would be nice. Actually, a worked out…
user678392
  • 451
  • 2
  • 6
  • 12
14
votes
3 answers

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 told me that we can use intuition and kindly refused…
user4220128
12
votes
1 answer

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 as follows: The machine has an infinite array A…
c c
  • 513
  • 4
  • 14
12
votes
1 answer

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 any functions $T(n),U(n)$, such that $U(n)$ is…
042
  • 706
  • 4
  • 10
11
votes
2 answers

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)? Intuition tells me not, since you need an…
zad
  • 318
  • 2
  • 7
11
votes
3 answers

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.) Could you please explain/point me to papers/books…
Dimiter
  • 129
  • 1
  • 4
11
votes
2 answers

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 have two objects (defined within the model) attract…
MJK
  • 111
  • 3
11
votes
1 answer

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 about some rules could anyone explain that?
iordanis
  • 247
  • 1
  • 2
  • 6
10
votes
1 answer

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 number of states? How can the Universal Turing machine…
Student
  • 275
  • 1
  • 5
9
votes
1 answer

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 lines? For context, I am a researcher who works on…
user168715
  • 221
  • 1
  • 5
1
2 3
…
12 13