Machines

Algorithms are essentially mechanical procedures, requiring no

intuition and capable of being carried out automatically by a
machine.
The basic operations (Le., reading, storing, controlling, and
processing a given set of initial or input data), various mechanical
models or abstract level machines can be designed to execute
any specific type of algorithm.
Three kinds of abstract machines with increasing degree of
capability, namely, (i) the basic machine, (ii) the finite state
machine, (iii) the Turing machine.
 BASIC MACHINE
A basic machine recognizes an input set I and produces an output set 0, where I and 0 are
finite. This kind of a machine is the'most primitive one where we are concerned with a set
of inputs and a set of outputs. In other words, the machine behaves like a function and
maps the input set I to the output set 0. call this function machine function (MAF)
Example 1:
In the case of Of gate, the output set 0 = {I, O}, and the input set I is a set of ordered pairs
of symbols 0, 1 given by I = {(O, 0), (0, 1), (1, 0), (1, I)}. The MAF of the or gate is given in
Table 2.1.

I (0, 0) (0, 1) (1, 0) (1, 1)

O 0 1 1 1
Example 2:
The standard weighing machine has an input set I = {coin} and output set 0 = {printed
weight ticket}.
Example 3:
In the conversion from binary-coded decimal to decimal digits,
I = {OOOO, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1OO1},
o == {O, 1, 2, 3, 4, 5, 6, 7, 8, 9}.
 Limitations
The basic machine has a very limited ability: it can only interpret a set of
input data and produce an output ·set which involves a combination of
the input. Hence, it is also called a combinatorial machine. Effectively, a
basic machine performs only a table look-up procedure, from tables of
finite size.
The basic machine has a very limited ability: it can only interpret a set of
input data and produce an output ·set which involves a combination of
the input. Hence, it is also called a combinatorial machine. Effectively, a
basic machine performs only a table look-up procedure, from tables of
finite size.
 FINITE STATE MACHINE
The finite state machine consists of a pair of functions, namely,
I x SO S [MAF],
I x S S STF(state function)].
The MAF maps the cartesian product of the input set I and the
state set S to the output set 0, whereas the STF maps the
cartesian product of the input set l and the state set S to the state
set S. The behaviour of such a machine can be completely
determined provided its initial state and the input are known. In
this machine, a set of final states (possibly empty from which the
machine can never reach other states) is also specified.
I = {(O, 0), (0, 1), (1, 0), (1, I)} = {i1, i2, i3, i4} ,
O = {0, 1} = {O1, 02},
S = {carry, no carry} = {S1,S2}.
 binary adder
State tables of binary adder 'a) Ix S  0 (MAF)
S/I Carry No carry
(0, 0) 1 0
(0, 1) 0 1
(1, 0) 0 1
(1, 1) 1 0
State tables of binary adder Ix S  S (STF)
S/I Carry No carry
(0, 0) No carry No carry
(0, 1) Carry No carry
(1, 0) Carry No carry
(I, 1) Carry Carry
TRANSITION GRAPH
It is more convenient to use a transition diagram (resembling a
flowchart) rather than state tables to represent an FSM. Such a
diagram is also known as a transition graph. It consists of labelled
circles to represent states and directed lines from each state Sk to
itself (loop) or to another state Sj. The directed lines are labelled1/
0 indicating that the input t E I causes the output 0 E 0 and shifts
the state Si E S to the state sj E S. It is clear that
Mealy Machine
is defined as a machine in the theory of computation whose output values are
determined by both its current state and current inputs. In this machine at most
one transition is possible.
It has 6 tuples: (Q, q0, ∑, ▲, δ, λ’)

Q is a finite set of states

q0 is the initial state
∑ is the input alphabet
▲ is the output alphabet
δ is the transition function that maps Q×∑ → Q
‘λ’ is the output function that maps Q×∑→ ▲
Moore Machine
Moore’s machine is defined as a machine in the theory of computation whose output values are
determined only by its current state. It has also 6 tuples

(Q, q0, ∑, ▲, δ, λ)
Q is a finite set of states
q0 is the initial state
∑ is the input alphabet
▲ is the output alphabet
δ is the transition function that maps Q×∑ → Q
λ is the output function that maps Q → ▲
FINITE AUTOMATA
FINITE AUTOMATA AND REGULAR EXPRESSIONS
Operators of RE
Precedence of RE Operators
EXAMPLES
Even number of a’s : The regular expression for even number of a’s is (b|ab*ab*)*.

String with ‘ab’ as substring : The regular expression for strings with ‘ab’ as substring is (a|b)*ab(a|
b)*.
RE to Automata
Context Free Grammars and
Language
Simple Expression in typical programming Language-limit to operator +, *
Leftmost and Rightmost Derivations
EXAMPLES
TURING MACHINE
Problems that Computers cannot Solve
 TM to accepts 0n1n

B000111B
BX00Y11B
BXX0YY1B
BXXXYYYB
B 00000100 B
B B0000110 B
B BB000111 B
B BBB00111 B
B BBB00BBB B
B BB000BBB B
B001000B
BBBB110B
SUBROUTINES in TM
0m10n1
Take 3x2=6
m=3
n=2
n 0s m times

B0001001BBBBBBBBB
subroutine call 1
BB001X010BBBBBBBB
BB001XX100BBBBBBB
BB00100100BBBBBBB
Subroutine call2
BBB01X01000BBBBBB
BBB01XX10000BBBBB
BBB010010000BBBBB
Subroutine call 3
BBBB1X0100000BBBB
BBBB1XX1000000BBB
BBBB1001000000BBB
BBBBBBBB000000BBB
THE MODEL OF LINEAR BOUNDED AUTOMATON
This model is important because (a) the set of context-sensitive languages is
accepted by the model. and (b) the infinite storage is restricted in size but not
in accessibility to the storage in comparison with the Turing machine model. It
is called the linear bounded automaton (LBA) because a linear function is used
to restrict (to bound) the length of the tape.
In this section we define the model of linear bounded automaton and
develop the relation between the linear bounded automata and context-sensitive
languages. It should be noted that the study of context-sensitive languages is
important from practical point of view because many compiler languages lie
between context-sensitive and context-free languages.
A linear bounded automaton is a nondetelministic Turing machine which
has a single tape whose length is not infinite but bounded by a linear function
UNIVERSAL TM
We now consider a very important question, namely, the construction of a
TM which is all powerful or universal in the sense that it is capable of doing
anything that any other TM can do. In other words, the universal Turing
machine (UTM) should have the capability of imitating any TM T given
the following information in its tape!
(i) the description of T in terms of its FM (operation or program
area of the tape);
(ii) the initial configuration of T, i.e., starting or current state and
the symbol scanned (state area of the tape);
(iii) the processing data to be fed to T (data area of the tape).
This obviously means that the UTM should have an imitation algorithm to
interpret correctly the rules of operation given in the FM of T.
The behaviour of the UTM is simple, namely, simulating T, one step at
time, as follows. It is guided by a marker to indicate the point on its tape
at which the description of T begins, and it keeps a complete account of
how the tape of T looks like at every instant. Also, it remembers the state
T is in, and the symbol T is reading. Then it simply looks at the description
of T to carry out what T is supposed to do. In order to exhibit this behaviour,
the UTM should have a table look-up facility and should perform
the following steps.
Step 1 Scan the square on the state area of the tape and read the symbol
that T reads and the initial state of T.
Step 2 Move the tape to the program area containing the FM, and find
the row in the FM headed by the symbol read in Step 1.
Step 3 Find the column headed by the state symbol in which T resides,
and read the triplets (i.e., new symbol to be replaced, new state, direction
of move) in the intersection of this column with the row found in Step 2.
Step 4 Move the tape to reach the appropriate square in the data area,
replace the symbol, move the tape in the required direction, read the next
symbol, and finally reach the state area and replace the state and scanned
symbois. Proceed to Step 1.
In order to convert this imitation algorithm into the FM of the UTM, we need to
note the following. Since we have only a linear tape on the UTM, we cannot
directly put on this tape the FM (which is a two-dimensional matrix) of T unless
some suitable device is used to codify the twodimensional information into a one-
dimensional form. Also, it is necessary that we have a suitable alphabet set I (for
the UTM) to include the external alphabet and the internal states of T. The
conversion of this algorithm can be achieved as follows:
(i) Encode the FM of T as a one-dimensional sequence of alphabets consisting of
groups of five symbols, namely, the row symbol, column symbol, and triplet. This
enables us to recover the information in a unique manner.
(ii) If we assume that there are altogether m distinct symbols, we can assign a
unique, suitable, easily decodable binary code to each of these
symbols with n or more bits, where 2n >= m, Once we have completed the
foregoing steps, we can encode the FM and the initial configuration of T into a
long binary sequence which is unambiguous
and unique and easily decodable by the UTM.
After the FM of T has been encoded, all we need to do is to express the imitation
algorithm as the FM ofUTM. This UTM will then solve the same problem as T.
The UTM laid the foundation for
(i) stored-program computers, and
(ii) interpretive implementation of programming languages.
 Decidability, Semi-Decidability, and Undecidability
Decidable Problems:
The decidable problems are those problems for which there exists a
corresponding Turing machine that halts on every input with an answer- yes
(accepting) or no (rejecting). It is also called Turing Decidable.

Semi-Decidable Problems :
Semi-Decidable problems are those problems for which a Turing machine halts
on the input accepted by it but can either loop forever or halt on the input which
is rejected by the Turing Machine. It is also called Turing Recognizable problems.

Undecidable Problems :
Undecidable problems are those problems for which there exists no Turing
machine which will always halt an infinite amount of time to give an answer as
‘yes’ or ‘no’. An undecidable problem has no algorithm to determine the answer
for a given input. It can be partially decidable but never decidable. They are also
known as Non-Recursively Enumerable Language.
 Solvability, Semi-8olvability, and Uasolvability
We now introduce the solvability (or computability) hierarchy for theproblems (or functions). This hierarchy
is (solvable == computable) C (partially solvable = partially computable)
C (totally unsolvable == non-computable).
Thus, if we are given a problem for algorithmic solution, only these three possibilities can arise. It should be
noted that we have introduced here a weaker concept, namely, partial solvability. We distinguish the three
cases
by using the Turing machine concept, as follows:
(i) If there is a TM (or algorithm) which, when applied to any problem in the class, always eventually
terminates with the correct yes/no answer, we call the problem solvable.
(ii) If there is a TM (or algorithm) which, when applied to any problem in the class, always eventually
terminates with the correct answer when the answer is yes and mayor may not terminate when the correct
answer is no, we call the problem semi-solvable or partially solvable.
(iii) If there is no TM (or algorithm) which, when applied to a problem in the class, eventually terminates with
the correct answer yes,
we call the problem unsolvable. The relationship between the solvable and partially solvable problems
is given by the following important theorem.
TM LIMITATIONS (UNSOLVABILITY)

For a given configuration of a Turing machine, two cases arise:

(i) The machine starting at this configuration will halt after a finitenumber of steps.
(ii) The machine starting at this configuration never reaches a halt,
no matter how long it runs.
We now ask the following question: Given any functional matrix, input data tape, and initial
configuration, is it possible to determine whether the process will ever halt? In other words,
we are asking for a decision procedure,
consisting of a single set of instructions, given once and for all, that will enable us to solve
the halting problem for every pair (machine, tape).
The answer is that the halting problem is unsolvable. To substantiate our answer, we shall
give a proof based on reductio ad absurdum.
 Consequences of the Halting Problem
We have just noticed that the halting problem is unsolvable by the Turing
machine. Using this, two important results can be proved:
(i) The empty-word halting problem of the TM is unsolvable, that is, there is no algorithm that takes an
arbitrary Turing machine A over an alphabet E as the input and determines whether or not A halts
for input of the empty word.

(ii) The uniform halting problem of the TM is unsolvable, that is, there is no algorithm that takes an
arbitrary A over an alphabet E as the input and determines whether or not A halts for every input.
The unsolvability of these halting problems implies the unsolvability of many other problems in
mathematics and in computer science. Such problems\are proved unsolvable by reducing the
unsolvability of the halting problem to the problems.
Some of the other results related to the halting problem are as follows:

(i) Can we decide whether a TM ever prints a given symbol a E I of its alphabet? This is unsolvable.

(ii) We know that we can mechanically check for equivalence (a) two combinatorial switching
circuits (namely, the Boolean expressions of the propositional calculus), (b) two sequential circuits,
and (c) the regular expressions describing two FSM's. However, two TM's with the same
alphabet cannot be checked for equivalence or inequivalence by an algorithm. That is, there is no
effective general way to decide whether a given computational process will ever terminate or
whether two given processes are equivalent.

(iii) There is an important theorem, called blank-tape theorem, which states that there exists a
Turing machine which, when started on a blank tape, can write its own description (Hennie, 1977).
This is of interest in constructing self-reproducing machines.
 Difference Between Decidability and Computability

Both computabilities, as well as decidability, tells us about the existence of an algorithm for a particular
problem or function, while solving a particular problem it becomes really important for us to figure out if the
problem is solvable or not, it is important both in terms of efficiency and execution. Determining both
computability and decidability is thus very important to figure out if the problem can be solved in a finite
amount of time. Even though both of them sound quite similar but there are subtle differences between
them. In this article, we will discuss briefly the differences between computability and decidability.
Computability:
The computability of a problem can be defined as whether it can be solved infinite amount of time. It is
connected with the idea that if there exists an algorithm to solve the problem.
Hence, we can define computability as the algorithmically computable problem or function. In another way,
we can define the computability of a problem or a function by its ability to be calculated by a Turing machine,
for the given input if the Turing machine halts and produces the output we can declare it as computable.
Decidability:
Decidability is a much simpler concept where we try to figure out for a given problem if there exists an
algorithm or a Turing machine that will halt within the given domain. The output to the decidable problem is
either YES or NO. Decidability is a generalized concept where we try to find out if there is a Turing machine
that accepts and halts for every input of the problem defined on the domain.
Rice’s Theorem
Every non-trivial (answer is not known) problem on Recursive Enumerable languages
is undecidable.e.g.; If a language is Recursive Enumerable, its complement will be
recursive enumerable or not is undecidable.

Reducibility and Undecidability

Language A is reducible to language B (represented as A?B) if there exists a function f
which will convert strings in A to strings in B as:

w ? A <=> f(w) ? B
Theorem 1: If A?B and B is decidable then A is also decidable.
Theorem 2: If A?B and A is undecidable then B is also undecidable.
Rice theorem states that any non-trivial semantic property of a language which is recognized by a Turing machine
is undecidable. A property, P, is the language of all Turing machines that satisfy that property.
Formal Definition
If P is a non-trivial property, and the language holding the property, Lp , is recognized by Turing machine M, then
Lp = {<M> | L(M) ∈ P} is undecidable.
Description and Properties
Property of languages, P, is simply a set of languages. If any language belongs to P (L ∈ P), it is said that L satisfies
the property P.
A property is called to be trivial if either it is not satisfied by any recursively enumerable languages, or if it is
satisfied by all recursively enumerable languages.
A non-trivial property is satisfied by some recursively enumerable languages and are not satisfied by others.
Formally speaking, in a non-trivial property, where L ∈ P, both the following properties hold:
Property 1 − There exists Turing Machines, M1 and M2 that recognize the same language, i.e. either ( <M1>, <M2>
∈ L ) or ( <M1>,<M2> ∉ L )
Property 2 − There exists Turing Machines M1 and M2, where M1 recognizes the language while M2 does not, i.e.
<M1> ∈ L and <M2> ∉ L
Proof
Suppose, a property P is non-trivial and φ ∈ P.
Since, P is non-trivial, at least one language satisfies P, i.e., L(M0) ∈ P , ∋ Turing Machine M0.
Let, w be an input in a particular instant and N is a Turing Machine which follows −
On input x
Run M on w
If M does not accept (or doesn't halt), then do not accept x (or do not halt)
If M accepts w then run M0 on x. If M0 accepts x, then accept x.
A function that maps an instance ATM = {<M,w>| M accepts input w} to a N such that
If M accepts w and N accepts the same language as M0, Then L(M) = L(M0) ∈ p
If M does not accept w and N accepts φ, Then L(N) = φ ∉ p
Since ATM is undecidable and it can be reduced to Lp, Lp is also undecidable.