startsWithZ is Uncomputable

Joseph Oforkansi, Aidan Dyga, Preston Smith

September 15, 2025

Introduction

  • Definition: startsWithZ(P, I) determines if the output of a program starts with “Z”.
  • Goal: Prove that startsWithZ(P, I) is uncomputable.
  • Motivation: Simple-looking questions about program behavior can be as hard as the Halting Problem, showing the limits of computation.
  • Real-World Connection: This reflects why compilers, program analyzers, and AI systems cannot perfectly predict every program’s output.

Building startsWithZ

  • Examples:
    • startsWithZ(“print(‘Zoo’)”, ““) →”yes”
    • startsWithZ(“print(‘Banana’)”, ““) →”no”

Proof By Contradiction

  • Assumption: Suppose startsWithZ is computable (always the opposite).
  • Trap (Logical Construction):
    • If we could implement startsWithZ, then we could also build:
      • startsWithZSelf(P): Checks if program P outputs a Z-string when given itself as input.
      • notStartsWithZSelf(P): Checks if program P outputs a NON-Z-string when given itself as input.

Building startsWithZSelf

Building notStartsWithZSelf

Proof By Contradiction Explained

  • Contradiction (Troublemaker Program): What happens when we run notStartsWithZSelf on itself?
    • If notStartsWithZSelf(notStartsWithZSelf) returns “Zebra”, then by definition, it should return “Apple”.
    • If notStartsWithZSelf(notStartsWithZSelf) returns “Apple”, then by definition, it should return “Zebra”.
  • Conclusion: Since assuming startsWithZ is computable leads to an impossible situation, our assumption must be wrong and it must be uncomputable.

What Can We Still Do

  • Options: While perfect analysis is impossible, we can still build practical tools to address many cases:
    • Static Analysis: Identifies bugs and unreachable code without running the program.
    • Dynamic Analysis: Identifies bugs and unreachable code by running the program.

Conclusion

  • Uncomputable: This problem is uncomputable once again as it comes down to the halting problem.
  • The notStartsWithZSelf program is a paradox: whenever it tries to decide if it itself outputs a string starting with “Z”, it is forced to give the wrong answer. No matter what it returns, the opposite should have been true. (Troublemaker Program)
  • This contradiction means there is no way to build a program that always correctly decides if another program outputs a string starting with “Z”.

Sources

  • Course Textbook
  • GitHub Copilot
  • Microsoft Copilot