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
8 votes
0 answers
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 ...
user avatar
  • 181
8 votes
1 answer
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-...
user avatar
8 votes
2 answers
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 ...
user avatar
7 votes
0 answers
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 ...
user avatar
  • 756
7 votes
2 answers
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 ...
user avatar
  • 1,207
5 votes
0 answers
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. ...
user avatar
  • 63
5 votes
0 answers
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 ...
user avatar
5 votes
0 answers
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 ...
user avatar
  • 51
5 votes
1 answer
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 ...
user avatar
  • 883
4 votes
0 answers
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}$) ...
user avatar
4 votes
0 answers
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 <...
user avatar
4 votes
0 answers
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 ...
user avatar
4 votes
0 answers
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. ...
user avatar
  • 386
4 votes
0 answers
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-...
user avatar
  • 493
4 votes
0 answers
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 ...
user avatar
  • 1,282
3 votes
0 answers
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 ...
user avatar
  • 31
3 votes
0 answers
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 ...
user avatar
3 votes
0 answers
84 views

Can we define CFL without grammars or automata?

The set of regular languages $R$ over an alphabet $\Sigma$ can be defined as the smallest set satisfying these 5 axioms: Empty language: $\{\} \in R$ Singleton languages: $\forall a \in \Sigma : \{a\}...
user avatar
  • 386
3 votes
0 answers
143 views

Why does using an encoding trick like Gödel numbers make a register machine universal?

Here the author describes the Random Access Stored Program machine and the problem of indirect addressing. The author states: But this does not solve the problem (unless one resorts to Gödel numbers)....
user avatar
  • 1,189
2 votes
0 answers
31 views

Universal register machine that recognizes the image of a partial function

Suppose $f$ is a $\mathbb N$-valued partial function over a subset of $\mathbb N$. If $f$ is computable by a universal register machine program, is the constant partial function $$ g:\text{image}(f)\...
user avatar
  • 21
2 votes
0 answers
50 views

Differences between a computation model and an abstract data type

I am wondering about the difference between an abstract data type (ADT) and a computation model. As I understand them: A computation model defines the basic unit of computation, that is, what can be ...
user avatar
  • 121
2 votes
0 answers
32 views

Reference/textbook on RAM model/model of computation for algorithms

Can someone recommend a reference/textbook on the RAM model of computation? Preferably something with a concise definition and doesn't get too much into computer architecture. I'm very fine with this ...
user avatar
2 votes
0 answers
41 views

A simple, concise, strong and a formal model of computation

Most mathematical objects can be said to be defined in simple terms, are usually really concise and still manage to capture the essence of what they are trying to talk about. For example, topology ...
user avatar
  • 10.8k
2 votes
0 answers
30 views

Generalizing Quantum Computation

When you first learn more about computation you can imagine it in terms of boolean circuits. That is you get a boolean vector $v \in \lbrace 0,1\rbrace ^n$ which you can then apply a circuit $C$ to ...
user avatar
2 votes
0 answers
60 views

Restrictions on Computational Methods (Art of Computer Programming)

In the Art of Computer Programming, Knuth describes a computational method as a quadruple $(Q, I, \Omega, f)$ where $I, \Omega \subseteq Q$, $\Omega$ is pointwise fixed, and each $x \in I$ defines a ...
user avatar
2 votes
0 answers
87 views

How does one program in a tag system?

I've played with 2-tag systems a bit and read all about tag/lag systems. They're great for experimenting with computation, and obviously useful as intermediaries in various proofs. My question is: ...
user avatar
  • 254
2 votes
0 answers
32 views

Similarities between Babbage's difference engine and the Turing machine

What would you consider similarities between the difference engine and the Turing machine? At this point I feel I know how they both function, yet I can't point out any worthwhile similarities between ...
user avatar
  • 21
2 votes
0 answers
830 views

Equivalence between different Turing Machines and a definition of simulation

Im having some difficulty understanding how the following two concepts could be related. Equivalence between TMs as is commonly tought According to this site answer, to prove a standard TM model to ...
user avatar
  • 21
2 votes
0 answers
46 views

Is the language $L$ of coded CFG's Turing decidable?

Consider the following language $L$ = {$<G><w>$ | $G$ is a CFG and $w\in L(G)$} Now, I wish to prove that $L$ is Turing decidable. My gut tells me to construct a Turing machine that ...
user avatar
2 votes
0 answers
749 views

What is the relationship between "model of computation" and "algorithm"?

Traditionally, the usual definition you find for model of computation is "an abstract description of how an output is computed given an input" (Wikipedia and my TCS course are my sources, but the ...
user avatar
  • 394
2 votes
0 answers
120 views

Simulating QC using nondeterministic Turing machine

Is it more efficient to simulate Quantum Computer using a non-deterministic Turing machine? Would it be more efficient than simulation using a deterministic Turing machine or probabilistic Turing ...
user avatar
  • 239
2 votes
0 answers
90 views

Is the set of admissible numberings recursively enumerable?

For each admissible numbering, pick at least one pair of programs (but not necessarily all, which is impossible anyway) where the first translates from a given admissible numbering to that one, and ...
user avatar
  • 478
2 votes
0 answers
384 views

Explaining TM notation in Lewis/Papadimitriou

I was working on some questions in the book "Elements Of The Theory Of Computation", by Lewis and Papadimitriou, and I need help with one question - question 4.1.8 (chapter 4): Give the full ...
user avatar
  • 90
2 votes
0 answers
55 views

Typed representation of a memory model

Assume a simple procedural language, where statements write and read from local memory via references and procedures accept arguments of n different scalar types (say floats, ints and strings) and ...
user avatar
  • 610
2 votes
0 answers
107 views

ORAM: Is it generic?

Recently, plenty of researchers are looking at designing efficient data-oblivious algorithms. Roughly speaking, an algorithm is said to be data-oblivious if its data access patterns are independent of ...
user avatar
  • 121
2 votes
0 answers
47 views

A linear code, what is that?

I have been trying to understand the polytope model used for loop nest optimizations. Now while going through some of the thesis written on this, i came across the term/phrase "linear code" a number ...
user avatar
2 votes
0 answers
69 views

Expressing classic automata in modern terms

This semester I was introduced to finite automata (FSM), then pushdown automata (PDA), and now the Turing machine (TM). Granted that there're many possible implementations of these abstractions (...
user avatar
2 votes
0 answers
76 views

NPDA, guessing capability and stack as an exclusive resource

Context Free languages is exactly the class of languages recognized by Nondeterministic Push Down Automata (NPDA). We can view a nondeterministic transition as a guess; for example if $L = \{x x^R \}$...
user avatar
  • 12.2k
1 vote
0 answers
21 views

What are practical applications for markovs algorithm(string rewriting systems)

:) Currently I am browsing through the internet on the hunt for a topic for my bachelors thesis. Whilst being on Reddit I discovered an interesting repo (https://github.com/mxgmn/MarkovJunior) for a ...
user avatar
1 vote
1 answer
57 views

A decidable language that can't be decided by a circuit ensemble of linear size

Let Size(O(n)) be the set of languages the can be decided by a circuit ensemble (a sequence of circuits C_i for every natural i s.t input size is i) such that every circuit's size is linear (in input ...
user avatar
1 vote
0 answers
54 views

Confused about the concept of deciding in nondeterministic Turing machines

I read this discussion before. However i’m still confused. I used to think a language decided by a NTM if for every input $w$ in $\Sigma^*$, all of the branches in computation tree leads to a halting ...
user avatar
1 vote
0 answers
37 views

CEK machine vs SECD machine

What are the differences between the CEK machine and the modern variant of the SECD machine (which combines stack and dump) from the point of view of performance, memory efficiency, and other factors? ...
user avatar
  • 386
1 vote
0 answers
32 views

Lack of "Any" scan for Turing Machines

I was reading Charles Petzold's The Annotated Turing that walks through Turing's original proof out of curiosity and feel like I've missed something during the part where Turing is describing ...
user avatar
  • 11
1 vote
0 answers
42 views

Puzzled by this interview problem of scheduling a computation graph on a single-processor under a memory constraint

I recently went through a interview session for a SWE/CS role at a well known company. It wasn't specifically a "coding-round" but was titled a "domain interview" session, so I ...
user avatar
  • 151
1 vote
0 answers
13 views

About the paper Privacy-preserving in association rule mining using an improved discrete binary artificial bee colony

I don't understand two parts in this paper: The min notion on page 4 line 357 (equation 10d): I understand this as to find all the $M_{10}$, $M_{11}$, $M_{01}$ first and then try to minimize the ...
user avatar
1 vote
0 answers
19 views

Computational Model for learning Computability and Complexity

I was reading the book by Kozen-Theory of Computation. There is a statement that Turing machine is the best model for defining basic time and space complexity because atleast for higher levels of ...
user avatar
1 vote
0 answers
568 views

Draw a CFG (context-free-grammar) that starts and ends with the same symbol yet has odd number of 1's

I figured out that the CFG that starts and ends with the same symbol in alphabet $\Sigma=\{0,1\}$ will be : S -> 0A0|1A1|0|1| A -> 0A|1A|𝜖 How can i interpret the odd number of 1's also?
user avatar
  • 11
1 vote
0 answers
60 views

If $A\in RE $ then $f(A)\in RE$

Let $A\in RE$, and define$f(A) = \{y |\ y= f(x),\ x\in A\}$ for some computable function $f$. Then $f(A)\in RE$. I can't figure out why this is true. Since $f$ is computable there is a Turing machine ...
user avatar
  • 317
1 vote
0 answers
381 views

How design a Deterministic finite automata which accept string starting with 101 and how to draw transition table for it if there is a dead state

I’m trying to design a DFA which accept string starting with 101 if the string start with 0 then it goes to dead state.Is my design is correct or wrong? And I don’t know how to draw transition table ...
user avatar
  • 11
1 vote
0 answers
42 views

Are there non-quantum, (potentially) realizable in the real world models of computation that allow a polynomial speedup over RAM?

I hear a lot about how quantum computers are a big thing because they allow solving some problems in polynomial time which we don't know how to do classically. As far as I understand it still isn't ...
user avatar
  • 428