Why focus on formal language in theory of computation? Most programs do more than merely accept or reject an input
Phoenix3875 @ Phoenix3875 @lemmy.world Posts 6Comments 270Joined 2 yr. ago
Phoenix3875 @ Phoenix3875 @lemmy.world
Posts
6
Comments
270
Joined
2 yr. ago
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.