Programming

It's because most of the hard questions and theorems can be phrased over the Booleans. Lawvere's fixed-point theorem, which has Turing's theorem and Rice's theorem as special cases (see also Yanofsky 2003), applies to Boolean values just as well as to natural numbers.

That said, you're right to feel like there should be more explanation. Far too many parser papers are written with only recognition in mind, and the actual execution of parsing rules can be a serious engineering challenge. It would be nice if parser formalisms were described in terms of AST constructors and not mere verifiers.

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.

But most useful programs we deal with do more than merely verify an input [...] We may sum a list of numbers [...]

Computers are binary. 1 or 0. Pass through the electrical gate; or do not pass through the gate. That's the only tool we've got to work with and therefore, "sum a list of numbers" is literally implemented as a series of "accept or reject" steps.

Everything above that is a convenient layer of abstraction. Abstraction is there to reduce your mental load while working but it doesn't always achieve that goal — especially if you don't know what's going on underneath.

Well what you are describing are the abstractions upon these models. So the 'basis' still remains true. Think of it this way:

• A modern machine is based on the RAM model;
• The RAM model is based on the register model;
• The register model is based on several lower-level abstractions, at the end of which we get to a Turing machine.

So AFAIK, Sipser's does not explain more intricate models like RAM machine or register machine, I recommend spending some time prompting ChatGPT or reading some books on it (don't know any off hand).

TL;DR: The formal languages described in Sipser's are the lowest levels of abstraction. Higher levels of theoretical abstractions do exist, which I described several here.

At the end, remember that theory and practice are to be used in tandem, neither will achieve anything alone. Modern languages we use today once resembled a formal, theoretical language, a PDA made of PDAs. Look at the earliest C compilers, for example: https://github.com/mortdeus/legacy-cc/tree/master/prestruct. It's just a giant state machine.

I highly recommend picking up an HDL (Hardware Description Language), or implementing one if you got the time. This shall give you a clear picture of how theory differs from practice.

PS: Modern systems languages also never give a true picture of what programming is, and what should it be about. I recommend picking up a language closer to functional than imperative. I recommend OCaml, or Haskell if could be. That is the other side of formality.

Language recognition is a useful framework for complexity theory. There are also "counting problems" and complexity classes for them, like #P:

https://en.m.wikipedia.org/wiki/%E2%99%AFP

If you're looking at numerical calculations from a theoretical standpoint, there is a variant of Turing machines for that, with a lot of really nice results:

https://en.m.wikipedia.org/wiki/Blum%E2%80%93Shub%E2%80%93Smale_machine