crashOnString is Uncomputable

Alexander Goddard, Miguel Orti Vila, Duru Akbas

September 15, 2025

Introduction

  • Computability theory explores what problems can or cannot be solved by algorithms, so if a problem cannot be solved by algorithms, it is uncomputable

  • crashOnString determines, given an input string and a program, whether it will crash or not.

  • At first glance, this seems possible; however, by building self-referential programs, we will prove that this creates contradictions.

  • This approach connects “crashOnString” directly to the Halting Problem; therefore, it is uncomputable.

Program sequence

Book Figure

Example hypothetical ‘crashOnString’

  • crashOnString takes as input a program and a string and then deterimes whether or not that program crashes on that string
  • Returns yes if program does crash and no if it doesn’t

Defining crashOnSelf

  from crashOnString import crashOnString
  def crashOnSelf(progString):
    return crashOnString(progString, progString)
  • crashOnSelf takes as input a program and deterimes whether or not that program crashes when run on itself
  • Returns yes if program does crash and no if it doesn’t

Defining weirdCrashOnSelf

  from crashOnSelf import crashOnSelf 
  def weirdCrashOnSelf(progString):
    val = crashOnSelf(progString)
    if (val == 'yes'):
      return 'did not crash!'
    else:
      # deliberately crash (divide by zero)
      x = 1 / 0
  • weirdCrashOnSelf takes an input program and then deterimes whether or not it crashes using crash on self
  • If the program crashes it returns without crashing
  • If the program doesn’t crash it will then force itself to crash
  • This program isn’t possible becuase when run on itself it produces a contradiction

Proof that crashOnString is uncomputable

  • crashOnString can be proven to be uncomputable through contradiction using weirdCrashOnSelf
  • When weirdCrashOnSelf takes itself as an input there are only two possiblities
    • if it crashes then \(val = yes\) which means it will return without crashing which isn’t possible becuase it cannot both crash and not crash
    • if it doesn’t crash then \(val = no\) which means it will go on to crash with a divide-by-zero which once again isn’t possible becuase it cannot both crash and not crash
  • Becuase both possibilties lead to a crontradiction we know that weirdCrashOnSelf isn’t possible
  • If we were to assume crashOnString is possible. Then we could use it to write both crashOnSelf and weirdCrashOnSelf. Although, we know weirdCrashOnSelf is impossible therefore our assumption isn’t correct and crashOnString must also be impossible

Conclusion

  • weirdCrashOnSelf is impossible and causes a contradiction with crashOnString
  • therefore crashOnString is uncomputable (and untractable)
  • when weirdCrashOnSelf takes itself as an input it creates a contradiction with crashOnString