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
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, ...
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 ...
102 views

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-...
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 ...
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, ...
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 ...
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 ...
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 ...
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. ...
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],...
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 ...
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 ...
97 views

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