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

477 questions
Filter by
Sorted by
Tagged with
27 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)\...
62 views

### prove that if L is context-free then L' = {w2#w1 | w1#w2∈L} is context-free

Given that $\#\notin \Sigma$ and $L\subseteq \Sigma^*\#\Sigma^*$, prove that if $L$ is context-free language then $L' = \{w_2\#w_1 \mid w_1\#w_2\in L\}$ is context-free. I'm trying to prove this in ...
1 vote
56 views

### Time Complexity of Exponentiation Operation as per RAM Model of Computation

Now, $\color{blue}{\text{Exponentiation}}$ is defined as Exponentiation is a mathematical operation, written as $b^n$, involving two numbers, the base $b$ and the exponent or power $n$, and ...
18 views

### Where are some examples of unsatisfiable formulas? Especially about 3CNF paradigm

I've been learning co-NP recently. I know that UNSAT $\in$ co-NP. So I want to find more examples of UNSAT, especially about 3CNF paradigm.
30 views

### Build a 2-PDA for language accepted by Turing Machine

I saw this question on the internet and found many solutions actually but none of them really persuade me that much. Question: Given language $L$ which is accepted by a Turing machine $M$, provide a 2-...
26 views

### How to represent mutually exclusive events in CSP

I am studying Communicating Sequential Processes (CSP), and I understand that an event can be "emmited" ($\overline{e}$) and an event can be "waited on" ($e$), so that an event ...
88 views

### Is ε a part of alphabet or property of alphabet and NFA in FA

I am reading chapter 1 of Michael Sipser's "Theory of Computation" and in the section "Formation defination of NFA" he says the following: 3rd point of the above image is the ...
51 views

### Turing Machine for the Language $L=\{(a^n)b(a^n)b(a^n) | n\geq0\}$

Turing Machine for the Language $L=\{(a^n)b(a^n)b(a^n) | n\geq0\}$ Here is what I have tried: 1. Starting State Read $a$, Write $x$, Move Right, Go To 2 Read $x$, Write $x$, Move Right, Go To 1 Read <...
19 views

### What is the computational class of neural networks?

What is the relationship between formal automata and the different types of neural networks? What kind of neural network would you need to be able to parse context-sensitive languages, for instance?
1 vote
51 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 ...
24 views

### Why are reachability trees meaningful for Petri Nets

To construct a reachability tree we start with the initial marking and then consider all enabled transitions and fire them one by one. That is, we find the marking corresponding to firing each. I can'...
103 views

26 views

### How does the railway model of computation get translated to motion on the heptagrid tiling of the hyperbolic plane?

I have been reading these, along with slowly chipping away at the two books Margenstern has produced: A universal cellular automaton in the hyperbolic plane A Universal Cellular Automaton on the ...
98 views

### How are two registers are enough to simulate a Turing machine?

The paper A universal cellular automaton in the hyperbolic plane says: Our simulation consists in simulating the execution of a register machine. It is known that two registers are enough to simulate ...
60 views

### Simplify $X'(X+Y) + (Y+X.X) ( X + Y') + Z + X.Z$

I wanna know if $X'(X+Y)$ means $X'.X+Y.X'$? Does it have an AND gate after $X'$? Notation: $X'$ : NOT $X$ $X + Y$: $X$ OR $Y$ (OR gate) $X.Y$ : $X$ AND $Y$ (AND gate) New to boolean, can't seem ...
1 vote
42 views

### Is a register machine built out of automata of some sort?

I am looking at register machines like the Random Access Machine. Wikipedia says: Random-access machine (RAM) – a counter machine with indirect addressing and, usually, an augmented instruction set. ...
101 views

### How do we define the term "computation" across models of computation?

How do we define the term computation / computable function generically across models of computation? Beginning with the textbook definitions of: {Linz, Sipser and Kozen} for "computable function&...
1 vote
130 views

### Given an algorithm, is it possible to find all other equivalent algorithms for the same computable function in the same model

For any computable-function, there may be multiple different algorithms (possibly countably infinite). For example, sort has many different implementations/algorithms, that we know of or that we have ...