longerThan10
is UncomputableSeptember 15, 2025
The short answer is “NO”, we can’t!
It’s UNCOMPUTABLE.
longerThan10
uncomputable?The Flow Diagram
LongerThan10(P,I)
- Return “yes”, if P
is greater than or equal to 10 characters on input I
- Return “no” otherwise
LongerThan10OnSelf(P)
- Return “yes”, if P
is greater than or equal to 10 characters on input P
- Return “no” otherwise
TroubleLongerThan10(P)
- If P
is at least 10 characters on input P
, return a string with fewer than 10 characters - Otherwise, return a string with at least 10 characters
This proves that LongerThan10
cannot exist because it produces a contradiction.
from TroubleLongerThan10
import TroubleLongerThan10
def TroubleLongerThan10(P)(progString):
val = TroubleLongerThan10(progString)
if val == 'yes':
# Return a string with fewer than 10 characters
return "short"
else:
# Return a string with at least 10 characters
return "this_is_long"
longerThan10
seems like a simple program.Questions?
Proofgrammers