Programming

17511 readers

441 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

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

submitted 8 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

[–] abhibeckert@lemmy.world 8 points 8 months ago* (last edited 8 months ago) (1 children)

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.

[–] matcha_addict@lemy.lol 4 points 8 months ago

I suppose you're right. But I thought the reason we are using conceptual models of computation is to not concern ourselves with the implementation details of the physical world and real computers. It's why we have an infinite tape, for example.

Representing a "sum a list of numbers" problem in terms of binary logic gates would be the opposite of that. We're complicating the problem. Turing machines as I've seen them are not that low level. Would binary addition be the sensible way to sum a list of numbers in a turing machine?

Your answer is still convincing though... I suppose we can represent functions as series of verifiers. But my only remaining point of confusion is... Is that really the better way?