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?
I’m not an expert in formal languages at all… But when I read your question, I was like “really?”
I mean yeah, when we talk about a program’s purpose we don’t often say “it verifies an input”. But what is verifying an input really? Deciding if a statement is true or false. And if you really want to, you can deconstruct almost anything any program does into components of that.
Should this UI element be displayed? Input: page visit, user, users preferences. Output: reject/confirm. Should the UI element be red? Should it be green?
And so on and so on for literally everything. Yeah, formal language theory is not strictly required for doing that, but it still is the foundation that is abstracted away. Same as you don’t need to know about the theory behind mathematical operations and classes and sets to do 1+1.
How would you represent something like “sum a list of numbers” as components of verifiers?
Here’s how I think it works
In formal language, what it means to accept a verification means does the result fall into the list of acceptable values.
Consider adding two 2-bit numbers:
The machine itself simply holds this automata and language, so all it does is take input and reject/accept end state. I think you’re just getting caught up in definitions
A sum of a list of numbers I think would be something like
Machines accept a valid state or hit an error state (accept/reject). The computation happens between the input and accept/reject.
But maybe I don’t understand it either. It’s been a while since I poked around at this stuff.
For all possible input, only recognize the one input that’s (under certain encoding scheme) equal to the sum of the given list. That’s for a given list.
Another more general approach is that, only recognize the input if (under certain encoding), it’s a pair of a list and a number, where the number is the sum of the list.
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.