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

379 questions
Filter by
Sorted by
Tagged with
3answers
1k views

### Is there a formalization of the computational model for quantum computers?

There are several equivalent computation models, each capable of simulating each other. For example, the lambda calculus or the SKI calculus which are based on rewriting, Cardelli's object calculus, ...
0answers
56 views

### Formal definition of simulation

Assume that the model of computation is a standard Turing machine model with input alphabet $\Sigma = \{0,1\}$, work alphabet $\Gamma = \{0,1,\_\}$, 1 input tape, 1 work tape and 1 output tape. We ...
1answer
102 views

0answers
62 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-...
1answer
181 views

### Precise definition of oracle classes $A^B$

I was reading in Papadimitriou's "Computational Complexity" book Chapter 14, about Oracle Machines. Papadimitriou defines, in definition 14.3, page 339-340, Oracle Turing Machines with oracle a ...
4answers
535 views

### Does a computer do only two things?

According to the book, Introduction to Computation And Programming Using Python by John V Guttag, a computer does only two things: Store data Manipulate data But is this all? I mean, without I/O, ...
1answer
59 views

### How to extent primitive recursion from natural numbers to finite strings?

Primitive recursion seems to be related to bounded quantification. It is easier to make sense of bounded quantification with respect to natural numbers than to make sense of bounded quantification ...
1answer
57 views

### Computing with number of stack items

For stack-oriented programming language, how many top-most items of the stack are needed to be accessible in order to be Turing complete? Is it enough to be able to access just the top-most item? Two ...
1answer
693 views

### recursive language and computable function

Question: Let $A$ and $B$ be finite alphabets and let $\#$ be a symbol outside both $A$ and $B$. Let $f$ be a total function from $A^{*}$ to $B^{*}$. We say $f$ is computable ...
2answers
2k views

### Meaning of ε in NFA-ε?

In wikipedia NFA-ε transition function defined as follows $Δ : Q × (Σ ∪ \{ε\}) → P(Q)$, where $Σ$ is an alphabet and $ε$ - empty string. I don't understand the meaning of $ε$ in this context. ...
1answer
66 views

### Is there a known algorithm for computing the n-th Turing machine directly? [duplicate]

Let us define a Turing machine by a machine description that is a string of symbols produced by some numerical encoding. For example, a Turing machine $M_1$ can be represented by 9,900,599 ([0 0 halt],...
1answer
163 views

### How can a Turing machine write the description of the n-th Turing machine?

I am trying to interpret the following problem: "Describe an algorithm for a Turing machine which receives the integer n as input and proceeds to write the description of the n-th Turing machine from ...
1answer
92 views

### Does “not regular” imply “acceptor needs memory”?

Regular Languages, by definition, can be accepted by finite automata, which do not have memory. But if I know that a language is not regular, does that imply that any mechanism that recognizes the ...
0answers
97 views

1answer
141 views

### Using analog values with Algebraic Normal Form?

Algebraic normal form (ANF) is a way of describing digital circuits made up of AND and XOR gates. The below is an example of an ANF expression which evaluates to true if two or more of it's three ...
1answer
75 views

### How does universal calculator work?

As I understand, the concept 'computation' started dependent on hardware (like looms for instance). The Hardware defines (physical cascades) what happens between input and output. I think I saw in ...
7answers
20k views

### Is a Turing Machine “by definition” the most powerful machine?

I agree that a Turing Machine can do "all possible mathematical problems". But that is because it is just a machine representation of an algorithm: first do this, then do that, finally output that. ...
1answer
232 views

### In automata theory, why is a machine classified based on the languages it recognises?

Automata Theory is a subject where we mathematically model a computing device and study the theory behind it. Here we group the computing devices based on the number of languages they can accept. ...