definedOnString is Uncomputable

Ainslee Plesko, Javier Bejarano Jimenez, & Abishek Dhakal

September 16, 2025

Introduction

• definedOnString(P, I) is designed to answer this question:
  • Return "yes" if program P(I) halts (is defined).
  • Return "no" otherwise.
• Uncomputable in the general case (see Halting problem)

definedOnString: Case 1

definedOnString: Case 2

Limitations

• definedOnString(P, I) is designed to answer this question:
  • Return "yes" if program P(I) halts (is defined).
  • Return "no" otherwise.
• definedOnString won’t run its input; will just analyze the code and decide if it halts or runs forever.
• Works fine for simple examples (like containsGAGA.py, yes.py, etc.)
• But since definedOnString is seeing whether the other program will halt or run forever, we already know that this is impossible (Halting Problem)
• The only way to do this program would be running the input with infinite time, to avoid false positives (program thinks it will run forever but it ends up breaking later) and false negatives (program does not break but thinks it will).
• This is not a bug or inefficiency, it’s a fundamental limitation of computation, which we found in the Halting Problem.

Why is it uncomputable?

• We already know that this program is uncomputable due to the Halting Problem, as this program needs to know if its input (a program) will halt or run forever.
• If we try to use this uncomputable program, we get a contradiction:
  • Assume definedOnString(P, I) exists
  • Define a new program:

from definedOnString import definedOnString

def weirdDefinedOnSelf(P):
    if definedOnString(P, P) == 'yes':
        while True:  # deliberately undefined
            pass
    else:
        return 'defined'

(cont.)

• Run it on itself: weirdDefinedOnSelf(rf('weirdDefinedOnSelf.py'))
• Case 1: Returns defined → program actually loops forever → contradiction
• Case 2: Infinite loop → program undefined → contradiction
• Both cases lead to contradiction → initial assumption fails
• Conclusion: definedOnString.py cannot exist.

Conclusion

• definedOnString(P, I) is uncomputable in the general case
• proof by contradiction:
  • we assume `definedOnString(P, I) exists and, therefore, can be created
  • we assume weirdDefinedOnSelf exists
  • weirdDefinedOnSelf acts as a troublemaker program
  • no program can return both yes and no -> logical impossibility
  • definedOnString(P, I) cannot exist