I want to design a system in which a program is sent along with data and then it answers with the result. Is redundancy a must in this situation to check for correctness of the processed data? What is enough to trust the other system? Please be aware that I might not be asking the right question, this is almost a philosophical question.
I think you can use fully homomorphic encryption to solve this problem.
Encrypt the program and data using a fully homomorphic encryption scheme, send it to the system to be processed, and retrieve the result. Let the correct output be the string $s$. Since you say that you might not be able to tell if $s$ is the correct output, I would have the program concatenate a prefix which you can verify. Something like:
The computation started at 'TimeStamp' and finished at 'TimeStamp' with the following result: $s$.
If the system made a mistake (or tried to cheat by not executing your program exactly), I am sure you could prove that with high probability (under standard complexity-theoretic assumptions), the decrypted output would not begin with
The computation started at 'TimeStamp' and finished at 'TimeStamp' with the following result:
where both occurrences of 'TimeStamp' are not only in the proper form of a time stamp, but also make sense as times (i.e. the first time is after you send the program to the system while the second time is after the first and probably shortly before the time the system gave you the results).