The Stack Overflow podcast is back! Listen to an interview with our new CEO.

# Questions tagged [computation-models]

The definition of the set of allowable operations used for computation and their respective costs. Some examples of models include Turing machines, recursive functions, lambda calculus, and production systems.

380 questions
Filter by
Sorted by
Tagged with
2k views

### Can a two-stack PDA accept language $a^nb^mc^nd^m$ which is not context-free?

Can a two-stack PDA accept language $L=\{a^nb^mc^nd^m \mid n \geq m\}$, which has no context-free grammar? I don't believe this has a context-free grammar, but please correct me if I'm wrong.
83 views

### Matching Lemma with infinitely many symbols

I was reading about Universal Turing Machines. I see that the matching lemma states, that between two symbols X and Y, if there are only 1-s and blanks, then a TM exists, which can count the number ...
2k views

2k views

### How can one simulate a PDA with a FIFO queue PDA?

I'm trying to figure out how a pushdown automata (PDA), which we know uses a stack (LIFO) can be simulated by a queue (FIFO). I understand that in a regular PDA, we only have access to the top most ...
348 views

### Mathematical model on which current computers are built

It is said that "The Turing machine is not intended as practical computing technology, but rather as a hypothetical device representing a computing machine. Turing machines help computer scientists ...
508 views

### Robustness of Turing Machines - 3 dimensional case

How can one show that a machine with a three dimensional memory arranged in an infinite grid can be simulated by a single-tape Turing machine? I'd imagine there's some sort of mapping possible from ...
356 views

### Quantum computing 'amplitudes'

As far as I understand, you receive an output from a quantum computer for an algorithm in the form of an amplitude, which is one of the many states your qubits may be in, however this amplitude is a ...
908 views

### Classfication of randomized algorithms

From Wikipedia about randomized algorithms One has to distinguish between algorithms that use the random input to reduce the expected running time or memory usage, but always terminate with a ...
9k views

### Differences and relationships between randomized and nondeterministic algorithms?

What differences and relationships are between randomized algorithms and nondeterministic algorithms? From Wikipedia A randomized algorithm is an algorithm which employs a degree of randomness ...
816 views

### What piece am I missing to turn this idea into a programming language?

I've been doing some reading (I'll name drop along the way) and have selected a few scattered ideas that I think could be cobbled together into a nifty esoteric programming language. But I'm having ...
113 views

### What constitutes one operation/cycle/move in the RAM model?

I saw a RAM model diagram that displayed an input tape, output tape, the program (read-only), the instruction pointer, and the memory registers. However, when I look at questions of time complexity, ...
968 views

### On-line simulation of a two-head tape Turing machine using single-head tape(s)

I have a question and I haven't been able to figure out the answer yet. I need to do the on-line simulation of a two-head tape Turing machine using single-head tape(s). I've found some online articles ...
3k 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 ...
963 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 ...
548 views

### 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 ...
574 views

### Turing Machine-Like Formalism for The Actor Model

Turing machines have a formal symbol alphabet, state and transition-rules based description of how a computation is done. The Actor Model is sometimes mentioned as a more powerful computational-...
1k views

### Is a PDA as powerful as a CPU?

This is a question I have stumbled upon in my exam revision and I find it intriguing: My computer is blue and it has a massive graphics card and a DVD and every- thing so which is more powerful: my ...
734 views

### $L(M) = L$ where $M$ is a $TM$ that moves only to the right side so $L$ is regular

Suppose that $L(M) = L$ where $M$ is a $TM$ that moves only to the right side. I need to Show that $L$ is regular. I'd relly like some help, I tried to think of any way to prove it but I didn't ...
1k views

### Please explain this formal definition of computation

I am trying to attack TAOCP once again, given the sheer literal heaviness of the volumes I have trouble committing to it seriously. In TAOCP 1 Knuth writes, page 8, basic concepts:: Let $A$ be a ...
333 views

### What is a good reference to learn about state transition systems?

I am studying different approaches for the definition of computation with continuous dynamical systems. I have been trying to find a nice introduction to the theory of "State transition systems" but ...
2k views

### What is required for universal analogue computation?

What operations need to be performed in order to do any arbitrary analogue computation? Would addition, subtraction, multiplication and division be sufficient? Also, does anyone know exactly what ...
2k views

### Quantum lambda calculus

Classically, there are 3 popular ways to think about computation: Turing machine, circuits, and lambda-calculus (I use this as a catch all for most functional views). All 3 have been fruitful ways to ...
400 views

### Notions of efficient computation

A polynomial-time Turing machine algorithm is considered efficient if its run-time, in the worst-case, is bounded by a polynomial function in the input size. I'm aware of the strong Church-Turing ...
1k views

### Is interaction more powerful than algorithms?

I've heard the motto interaction is more powerful than algorithms from Peter Wegner. The basis of the idea is that a (classical) Turing Machine cannot handle interaction, that is, communication (input/...