MathDB

We have a machine that has an input and an output. The input is a letter from the finite set

I

and the output is a lamp that at each moment has one of the colors of the set

C=\{c_1,\dots,c_p\}

. At each moment the machine has an inner state that is one of the

n

members of finite set

S

. The function

o: S \rightarrow C

is a surjective function defining that at each state, what color must the lamp be, and the function

t:S \times I \rightarrow S

is a function defining how does giving each input at each state changes the state. We only shall see the lamp and we have no direct information from the state of the car at current moment. In other words a machine is

M=(S,I,C,o,t)

such that

S,I,C

are finite,

t:S \times I \rightarrow S

, and

o:S \rightarrow C

is surjective. It is guaranteed that for each two different inner states, there's a sequence of inputs such that the color of the lamp after giving the sequence to the machine at the first state is different from the color of the lamp after giving the sequence to the machine at the second state. (a) The machine

M

has

n

different inner states. Prove that for each two different inner states, there's a sequence of inputs of length no more than

n-p

such that the color of the lamp after giving the sequence to the machine at the first state is different from the color of the lamp after giving the sequence to the machine at the second state. (b) Prove that for a machine

M

with

n

different inner states, there exists an algorithm with no more than

n^2

inputs that starting at any unknown inner state, at the end of the algorithm the state of the machine at that moment is known. Can you prove the above claim for

\frac{n^2}{2}

Problem Statement