# Tagged Questions

The tag has no wiki summary.

238 views

### Is there a model of computation, that tries to be realistic? [on hold]

For instance, the tape on a Turing machine is infinite, where as we usually only have a finite amount of available memory. Secondly Turing machines are not really convenient IMHO for proving things ...
26 views

### Simulating a Turing Machine with finite memory with a regular TM [closed]

A Turing Machine with memory is defined just like a regular TM, with the addition of finite memory size n and the transition function d(mem). At each step, the transition depends on the current state, ...
92 views

### Which computational model is used to analyse the runtime of matrix multiplication algorithms?

Although I have already learned something about the asymptotic runtimes of matrix multiplication algorithms (Strassen's algorithm and similar things), I have never found any explicit and satisfactory ...
151 views

### Automaton equivalent of the π calculus?

If Turing Machines are the automata equivalent of the $\lambda$ calculus, what is the automaton equivalent of the $\pi$ calculus? I suppose it would be some class of automata that resembled a Turing ...
71 views

### Difference between Analytical and Difference Engines

I'm not sure if one can compare the two, mainly because what I've read so far, I didn't quite understand, but what are the key differences between these 2 engines?
114 views

### construct a TM from a PDA

Given a PDA $P=(Q,\sum,\delta,q_0,F)$ construct formally a TM that accepts $L(P)$. My idea is to construct a Turing machine with 2 tapes, one for the input and the other for the stack. Also to add ...
143 views

### Which theoretical parallel model is closest to CUDA?

Which theoretical parallel model is closest to CUDA/OpenCL programming model? For example, it fits at some degree to the generic Parallel Random Access Machine (PRAM) model. However, that is too ...
280 views

### Parallel merge sort using hypercube connection template

I've been reading about hypercube connection template for parallel algorithms. The general scheme is explained in Designing and Building Parallel Programs by Ian Foster and it's pretty clear. What I ...
382 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.
58 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 ...
188 views

### Does forcing TMs to change all symbols they read change their power?

If we limit a turing machine so that it is not allowed to write the symbol that it reads would it reduce its power? For example: $( State, A, State, Z, DIRECTION)$ $A$ cannot be the same symbol as ...
395 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 ...
208 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 ...
145 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 ...
167 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 ...
2k 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 ...
525 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 ...
82 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, ...
195 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 ...
382 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 ...
277 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 ...