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

104 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
148 views

### Make a tag system simulate a finite automaton?

Tag systems are Turing-complete. I was wondering if there is any easy way to create tag systems that simulate finite automata. So create tag systems that recognize languages, e.g. by having at the end ...
779 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-...
2k views

### What is the difference between quantum computing and parallel computing?

Quantum computing essentially relies on the fact that qubits maintain multiple possible states simultaneously. Parallel computing too processes multiple states simultaneously. So what is the ...
103 views

### Automata that is Turing complete if you add a nondeterminism

Pushdown automata have an interesting property: non-deterministic ones belong to a different computational class than deterministic ones. This is in contrast to finite state and turing machines, for ...
418 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 ...
369 views

### Time complexity of languages recognized by linear bounded automata with restricted number of writes

Suppose that $L$ is a language recognized by a linear-bounded automaton with the constraint that it can only change each of its input cells at most $t$ times each, where $t$ is some constant integer. ...
230 views

### Computational power of Actor Model

In the question below, let TM be Turing machine, NTM be nondeterministic Turing machine and PTM be probabilistic Turing machine. In his paper "Actor Model of Computation: Scalable Robust Information ...
113 views

### Model Join calculus as hypergraphs

I'm not sure if this is the right site to ask, but I couldn't find a another one. Some time ago I found out about the join calculus. It is based on constructs called joins to support concurrency. For ...
173 views

### Advances in recent time in Von-neumann self replication idea

I have read about Von-neumann self replication from Theory of Self-reproducing automata, which are lecture notes reconstructed from lectures in book of the same name. Theory of Self-reproducing ...
94 views

### Necessity of encoding for certain models of computation

Consider the following model of computation (from here). Although Fractran is Turing-complete, it assumes that the "user" is able to perform the steps of encoding the input ($2^{n + 1}$) ...
75 views

### The cost of memory allocation on the (tacitly assumed) Word RAM machine?

Consider a particular algorithm that solves the binary search problem (or similar stuff) by performing $\sqrt{n}$ simple operations on numbers of $\log(n)$ bits. Suppose this algorithm works on a <...
73 views

### Real RAMs with "reasonable" operations

There is a large body of literature on RAMs with "reasonable" and "unreasonable" operations, where "unreasonable" operations would yield a machine with too much power to be practically feasible. For ...
186 views

### What is the computational class of a reduced Wang B-machine?

A Wang B-machine is Turing-complete and has only 4 instructions: right: Move head right. left: Move head left. ...
71 views

### What is the role of abstract machines in the Curry-Howard isomorphism?

By abstract machines I mean things like the SECD machine, Krivine's machine or more generally machines with states/memory/registers/stack/accumulator... According to Wikipedia page of the Curry-...
45 views

### Computational complexity of emulating (untyped) λ-calculus with a queue machine

I am looking for bounds - both lower and upper - on the time, spacial, and state/symbol (i.e. number of states and symbols required) complexity of simulating the (untyped) λ-calculus with a queue ...
63 views

### Is there an abstract architecture equivalent to Von Neumann's for Lambda expressions?

In other words, was a physical implementation modelling lambda calculus (so not built on top of a Von Neumann machine) ever devised? Even if just on paper? If there was, what was it? Did we make use ...
98 views

### Alternative to a CALL as a composition?

I've seen a numerous interesting abstract machines (i.e. CESK) and evaluators (diverse meta-circular S-expression evaluators, i.e. vau, COLA) and other models (concatenative, SK/Lambda calculus) which ...
84 views

1 vote