0
$\begingroup$

For a Finite State Automaton / Finite State Machine (FSM) $F$, that has an input alphabet, a set of possible states, an initial state, a set of possible final states and a state transition function, let a finite input sequence $S$ is given, such that at the end of this sequence the FSM enters a final state and stays in that state.

Can this FSM $F$ along with the input sequence $S$ be considered a separate FSM $F'$?

Analogous to this, can a Turing machine $T$ along with a finite tape $P$ be considered a separate Turing machine $T'$?

What are the conditions, if any, for this to be true assuming it is true?

Note: I expect a formal proof, or a reference/outline to a formal proof that proves that either of this can or cannot be done. Some theory related to this is also welcome.

My research:

Closely related topic:

R. T. G. TAN (1979) Hardware and software equivalence, International Journal of Electronics, 47:6, 621-622, DOI: 10.1080/00207217908938690

I am aware of the principle of hardware and software equivalence, which states that a given task can be performed using hardware or software, i.e. digital hardware and software are equivalent models of computation. But I think my question is different from this one.

Motivation:

  • From this question ( Is there code below microcode? ) I think we can consider an FSM with its input sequence (microcode) to be a part of another FSM (the digital computer), but of course much more circuitry like Arithmetic and Logical Unit (ALU) and datapath is needed to make a computer. Microcode is used only for the control circuit.

  • This answer claims the data in the RAM of a computer along with the CPU can be considered to be a part of a bigger circuit.

To quote:

The circuit is fixed (it is the gates in the processor) and part of its input is data that depends upon the program you are executing (which is stored in the RAM of the computer). However, you could consider this a larger circuit where part of it is hardcoded (i.e., the program part of the input is hardcoded); then you can view a computer running a program as a big circuit with part that is universal and identical for all programs (the gates of the processor) and part that depends on the program (the hardcoded input), and this immediately gives a mapping from programs to circuits. The mapping is implemented by a compiler.

$\endgroup$
1
$\begingroup$

It's not clear to me how to interpret "can be considered", so I'm going to identify one technical question that can be answered.

Given a FSM $F$ and an input sequence $S$, it is possible to build another FSM $F'$ so that the execution of $F'$ on the empty input is in one-to-one correspondence with the execution of $F$ on $S$ (and in particular, both end at the same end state(s); e.g., either $F$ accepts on $S$ and $F'$ accepts on the empty input; or $F$ rejects on $S$ and $F'$ rejects on the empty input).

The proof is a straightforward application of the product construction: we construct one FSM $F_0$ that outputs the fixed sequence $S$, and then compute the parallel composition of $F_0$ with $F$.

The following is also true: given a Turing machine $T$ and a fixed input $P$ (i.e., initial state of the tape $P$), then it is possible to construct another Turing machine $T'$ such that execution of $T$ on input $P$ has the same result as execution of $T'$ on any input.

Formal proofs with Turing machines are often tedious and uninformative, so it's easier to see how this is true by considering a real-world program. For instance, suppose we have Python code that defines some function t():

def t(x):
    ...

and we have some fixed string p. Consider the following Python function t':

def t(x):
    ...
def t'(x):
    return t(p)

Then it is easy to see that the behavior of t' on any input is equivalent to the behavior of t on input p. (Here we have hard-coded a lexical constant string in the place indicated with p above.) You can do the same thing with Turing machines, where the machine first writes $P$ on the tape, and then starts executing $T$, to define a Turing machine $T'$ that proves the claim above.

$\endgroup$
3
  • $\begingroup$ To clarify, this machine $T'$ with the fixed output for all inputs is a Turing machine? $\endgroup$ Mar 1 at 6:05
  • $\begingroup$ @ShashankVM, Yes, $T'$ is a Turing machine. $\endgroup$
    – D.W.
    Mar 1 at 6:12
  • $\begingroup$ Just to inform, I have asked another question here based on our conversation on this answer. cs.stackexchange.com/q/136049/115941 $\endgroup$ Mar 1 at 6:41

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.