The machine-models tag has no wiki summary.
4
votes
1answer
41 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 ...
0
votes
0answers
30 views
Why set or reset a Turing computer and how is a reset function implemented?
Turing and other computer configurations are set and reset to initial conditions.
What is/are the initial condition(s) for a Turing computer configuration?
Set and reset are glossed over and never ...
4
votes
2answers
148 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.
3
votes
2answers
37 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 ...
6
votes
1answer
179 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 ...
1
vote
1answer
165 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 ...
6
votes
2answers
184 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 ...
3
votes
2answers
103 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 ...
8
votes
1answer
111 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 ...
10
votes
4answers
1k views
Differences and relations between randomized and nondeterministic algorithms?
What differences and relations are between randomized algorithms and nondeterministic algorithms?
From Wikipedia
A randomized algorithm is an algorithm which employs a degree of
randomness as ...
5
votes
3answers
288 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 ...
2
votes
1answer
68 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, ...
4
votes
1answer
128 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 ...
8
votes
3answers
189 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 ...
8
votes
1answer
180 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 ...
8
votes
1answer
162 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 ...
8
votes
3answers
124 views
Is there an abstract machine that can capture power consumption?
When reporting algorithmic complexity of an algorithm, one assumes the underlying computations are performed on some abstract machine (e.g. RAM) that approximates a modern CPU. Such models allow us to ...
