this post was submitted on 28 Mar 2024
33 points (100.0% liked)

Programming

17443 readers
150 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

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
33
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
9 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
[–] solrize@lemmy.world 2 points 7 months ago

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