1
$\begingroup$

From https://en.wikipedia.org/wiki/Abstract_machine

A typical abstract machine consists of a definition in terms of input, output, and the set of allowable operations used to turn the former into the latter.

The best-known example is the Turing machine.

  1. In a Turing machine, what is its set of operations?
  2. Is $\delta$ in the following definition of a Turing machine an operation? (If yes, then there is only one operation in a Turing machine?) Thanks.

    From https://en.wikipedia.org/wiki/Turing_machine

    a (one-tape) Turing machine can be formally defined as a 7-tuple $M= \langle Q, \Gamma, b, \Sigma, \delta, q_0, F \rangle$ where

    $Q$ is a finite, non-empty set of states

    $\Gamma$ is a finite, non-empty set of tape alphabet symbols

    $b \in \Gamma$ is the blank symbol (the only symbol allowed to occur on the tape infinitely often at any step during the computation)

    $\Sigma\subseteq\Gamma\setminus\{b\}$ is the set of input symbols

    $q_0 \in Q$ is the initial state

    $F \subseteq Q$ is the set of final or accepting states.

    $\delta: (Q \setminus F) \times \Gamma \rightarrow Q \times \Gamma \times \{L,R\}$ is a partial function called the transition function, where L is left shift, R is right shift.

$\endgroup$
  • $\begingroup$ This actually defines only deterministic Turing Machines. For non-determinism, $\delta$ must be a relation. $\endgroup$ – babou Oct 31 '14 at 9:12
  • $\begingroup$ Don't you answer your own question? $\endgroup$ – Raphael Oct 31 '14 at 9:51
2
$\begingroup$

The set of operations is what makes the machine work, i.e. read input somewhere, write output somewhere, and change its internal state (which includes anything it may change in its memory which can be a tape or some other device).

In the case of a TM, that is done by the transition function $\delta$.

Now, as you wish, you may see the transition function (actually a relation, when non-deterministic)) as the unique operation applied repeatedly. Alternatively you may consider that each instance of the (arguments, effect) pairs defined by the function, usually defined on a finite number of possible arguments pairs (state, tape content), each associated with a finite number of effect triples (state,tape output,move), are as many separate instructions, the transition relation being then the instruction set.

It is not a fundamental issue to decide whether you see it globally or case by case.

$\endgroup$
1
$\begingroup$

The Wikipedia definition makes more sense for machines like the RAM machine in which the "program" looks more like a program. Let me first give an example, and then explain what the counterpart is for Turing machines. In any case, the term "allowable operation" is informal, though the notion of abstract machine can be made formal, for example in the work of Yuri Gurevich.

A RAM machine is one in which the program looks very much like C code. Memory cells and registers (both unbounded) hold bounded-size integers, the exact bound depending on the input length. The machine supports integer arithmetic, bitwise operations, and comparison operations. One can think of other variants, for example the basic data type could be unbounded integers, or even unbounded reals ("real RAM"). We can also allow more basic operations: square root, general powers, logarithm, exponential, and so on. These variants can effect the computational complexity, but usually don't change the Turing-completeness of the model.

The Turing machine model is very primitive. The basic operations are very weak – the machine can read and write symbols, the head moves to the left or to the right, and that's all. Turing machines are also programmed differently.

One can imagine a Turing machine in which each cell would contain an integer. The control would have to be defined somewhat differently – for example, perhaps the decision what to do next could depend on comparing the current value to a value in some register, and then the allowed operations would be to copy some value to some register or from register to a cell, basic arithmetic on registers, and so on. But that would be quite a different model, one which I don't recall having ever seen.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.