Programming

17408 readers

68 users here now

Welcome to the main community in programming.dev! Feel free to post anything relating to programming here!

Cross posting is strongly encouraged in the instance. If you feel your post or another person's post makes sense in another community cross post into it.

Hope you enjoy the instance!

Rules

Follow the programming.dev instance rules
Keep content related to programming in some way
If you're posting long videos try to add in some form of tldr for those who don't want to watch videos

Wormhole

Follow the wormhole through a path of communities !webdev@programming.dev

founded 1 year ago

MODERATORS

snowe@programming.dev

Ategon@programming.dev

MaungaHikoi@lemmy.nz

Why focus on formal language in theory of computation? Most programs do more than merely accept or reject an input (lemy.lol)

submitted 7 months ago by matcha_addict@lemy.lol to c/programming@programming.dev

10 comments fedilink hide all child comments

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?

you are viewing a single comment's thread
view the rest of the comments

[–] ChubakPDP11@programming.dev 3 points 7 months ago

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.