Questions tagged [machine-models]

The tag has no usage guidance.

11 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
26
votes
0answers
424 views

Adiabatic quantum computing with level crossings

Question. In adiabatic evolution, to ensure that the ground state high overlap with the unique ground state of the system (i.e. to achieve arbitrarily small error) using adiabatic theorems, it is ...
15
votes
0answers
1k views

Can a Penrose tile cellular automaton be Turing-complete?

This question was based on an incorrect premise ... see Colin's comment below. Forget it. This was inspired by the discussion on this Math Overflow question. First, I need to define our terms. In a ...
10
votes
1answer
363 views

Reversible Turing tarpits?

This question is about whether there are there any known reversible Turing tarpits, where "reversible" means in the sense of Axelsen and Glück, and "tarpit" is a much more informal concept (and might ...
8
votes
0answers
161 views

Cell probe model vs transdichotomous ram

can someone explain me the difference between those two (cell probe model and transdichotomous ram)? In cpm I'm allowed to do computation for free, and complexity of algorithm is just a number of ...
7
votes
0answers
143 views

What can you do with a moving knife besides cutting a cake?

In the fair cake-cutting, two different computational models are used: A discrete model, in which the algorithm issues queries to the players and proceeds according to their replies; A continuous ...
3
votes
0answers
223 views

Convention for RAM machine models

When algorithm asymptotic runtimes are given without explicitly noting the computational model, what is the convention for the exact model used? My understanding is that most problems use unit-cost ...
3
votes
0answers
78 views

Is there research on “minimal” Turing-universal Markov algorithms?

The Markov algorithm is a simple model of computation. For other models of computation, such as Turing machines, cellular automata, tag systems, etc., there is research on the "minimal" instances of ...
1
vote
0answers
82 views

Implication of lower bounds in Boolean circuit to other models of computation

Suppose that one can prove that some hard function $f$ with $n$ bit input does not admit any Boolean circuit of size at most $n^t$. Then, how strong can we say about how hard $f$ is in other models? ...
1
vote
0answers
170 views

What is the the optimal computational model for memristive style CMOS?

I'm a bit new to the practical use of memristors in general, but I'm starting to see it as a (3D stacked) grid of components that could be treated as transistors or flip-flops on demand (which may be ...
0
votes
0answers
77 views

Understanding MA protocol as a variant of TM for small space setting

MA protocol is one of the most basic models of interactive proofs. Merlin is a prover sending a witness $w$ for given input string $x$, and Arthur is a verifier who verifies if $w$ is a positive ...
0
votes
0answers
68 views

Machine models based on group-labeled digraphs?

Following an earlier question, I would like to suggest the following generic computation model. Let $\Gamma$ be a group, we say that a $\Gamma$-labeled digraph is a digraph $G$ whose arcs are labeled ...