Search code examples
computer-sciencetheorem-proving

Is it possible to describe a function that is impossible to implement?

I am studying Theoretical Computer Science and I encountered this question:

Give example of a function that takes N as input and outputs (Yes,No) such that there is no Java program that can implement this function.

How would I go about solving this? I must not be understanding this correctly, because I feel like a Java program can always be made from the statement given above.

Solution

  • If I understand the question correctly, any undecidable decision problem would be a correct answer.

    The halting problem is the most famous undecidable problem, and you could use a Gödel numbering to encode any input program as a number N.