While reading Sipser’s book on theory of computation, it relies heavily on the concept of formal language, and machines that merely accept or reject an input.
But most useful programs we deal with do more than merely verify an input. They compute something. We may compute a solution for an equation instead of merely verify it. We may sum a list of numbers, or calculate some function on it.
Maybe “most” is an exaggeration since I can’t prove it. But still, it begs the question. Why not deal with machines than do more than merely verify?
In general, given a Turing machine which outputs the result of a procedure to its memory tape, you can equivalently construct a recognizer of valid input/output pairs. Say P is the procedure, then the recognizer R is
let (i, o) = input in P(i) = oThe reverse is also possible. Give a recognizer R, you can construct a procedure P that given part of the input (can be empty), computes the rest of the input that makes R accept the whole. It can be defined as
for o in all-strings, if R(i, o) then output o and halt, else continue.It might feel contrived at first, but both views can be useful depending on the situation. You’ll get used to it soon with some exercises.