this post was submitted on 28 Mar 2024
31 points (100.0% liked)
Programming
16781 readers
108 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 [email protected]
founded 1 year ago
MODERATORS
you are viewing a single comment's thread
view the rest of the comments
view the rest of the comments
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.
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.