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?

  • @[email protected]OP
    5•8 months ago

    How would you represent something like “sum a list of numbers” as components of verifiers?

    • @[email protected]
      6•8 months ago

      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:

      • Alphabet: { 0, 1}
      • Language: x x consists of four binary digits representing two 2-bit binary numbers where the result of adding these two numbers is a valid 2-bit binary number (i.e. falls between 00 and 11)
      • Then you have an automata that will:
        • Start from the rightmost bit
        • Add the corresponding bits (+ carry from any previous iterations)
        • Carry over to the left if needed
        • Repeat for both bits
        • Check for acceptance
      • Machine as a whole simply checks did the inputs produce a valid 2-bit number, so it just accepts or rejects

      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

      • Alphabet: digits 0-9 and ‘,’
      • Language: a single string of digits or a single string of digits followed by a comma and another valid string
      • Automata:
        • Are we a single string of digits? If yes, accept
        • Sum the last number into the first and remove the comma
        • Repeat
      • Machine: Does the some operation result in a valid string?

      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.

    • @Phoenix3875
      3•8 months ago

      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.

      • @Phoenix3875
        3•8 months ago

        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) = o

        The 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.