yesOnString is Uncomputable

Benedek Kaibas, Issei Hasegawa, Cullen Doyle

September 15, 2025

What is yesOnString?

  • Decision problem

    • Inputs: A Python program (P), A string input (s)

  • Question: Does program P, when run on input s, return “yes”?

  • When does the program return “no”?

    • Invalid program, undefined output, non-“yes” as a program return

Code

Proof By Contradiction

  • Assumption:
    • Suppose yesOnString exists.
  • Self-referential program D:
    • If yesOnString(x, “x”) = Yes -> D outputs nothing.
    • If yesOnString(x, “x”) = No -> D outputs “x”.
  • Self - application (x = “D”)
    • If result = yes -> D does not output “D” -> actually not “Yes”
    • If result = no -> D outputs “D” -> actually Yes
  • Conclusion:
    • The decider’s prediction always contradicts the actual behavior

Proof By Contradiction with Coding

  • We get an infinite chain of function calls

Output of the Proof by Contradiction

Image One Image Two

Similarity to Halting Program

Self-reference
– Halting: a program halts on its own input.
– yesOnString: a program outputs “yes” on itself.

Decider → paradox
– A universal decider cannot exist.
– The “troublemaker” flips/loops.

Non-termination
– Matches Turing’s proof of undecidability.

Similarities between the Halting Problem and the yesOnString

  • Both rely on self-reference
  • Both assume a universal decider → leads to paradox
  • Both produce infinite loops or recursion in code demos
  • Both are undecidable problems
  • Both reveal the limits of computation

Conclusion

  • Our code attempts to decide yesOnString but quickly falls into recursion or infinite loops.
  • The “troublemaker” example proves that self-referential programs break any decider.
  • Running the halting demo shows how undecidability appears in practice, not just theory.
  • These simple experiments reveal the real limits of what algorithms can compute.