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

463 questions
Filter by
Sorted by
Tagged with
789 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, ...
361 views

### RAM Machine and FSM

I heard that it's possible to model a bounded-memory RAM as a Finite State Machine. I'm curious about the method of how we would do that. How would you model a bounded-memory RAM as a Finite State ...
123 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 ...
69 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 ...
705 views

### Are partial recursive functions analogous to recursive languages or r.e. languages?

From Ullman and Hopcroft's Introduction to Automata Theory, Language, and Computation 1ed 1979: The assumption that the intuitive notion of "computable function" can be identified with the class ...
4k 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. ...
90 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],...
260 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 ...