Proving that `longerThan10` is Uncomputable

Grant Anderson, Coltin Colucci, Ritesh Ojha

September 15, 2025

Introduction

Goal : Prove that program longerThan10 is uncomputable in the general case.

What is Longerthan10 Program?

This program takes two parameters (P, I).
Returns “yes” if P(I) is a string of more than 10 CHARACTERS
Returns “no” otherwise

Can we write a program that computes longerThan10?

The short answer is “NO”, we can’t!

It’s UNCOMPUTABLE.

Why is `longerThan10` uncomputable?

The Flow Diagram

If longerThan10 were possible, we could solve the famous Halting Problem and we know its impossible to solve the Halting Problem. So longerThan10 is uncomputable.

Program Name and Behavior

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.

“Code”

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"

This is non runnable Python code that shows the logic of the “Longer than 10” issue and why it cannot exist.

Overview and Q&A

At first glance, longerThan10 seems like a simple program.
But when we try to construct it in the general case, we end up with the same contradiction that arises in the Halting Problem.
This shows how limits of computability apply not just to exotic problems, but also to ones that seem straightforward.

Questions?

Proving that longerThan10 is Uncomputable