countLines is Computable

Hemani Alaparthi, Hannah Brown, Anupraj Guragain, Molly Suppo

September 15, 2025

Introduction

Can a program analyze itself? What happens when we create programs designed to contradict their own behavior?

  • Programs can count lines in other programs - even themselves!
  • But what if we intentionally create contradictory behavior?
  • We’ll explore a flawed proof that tries to show countLines is impossible
  • Spoiler: The proof fails, and countLines is definitely computable!

Implementing the countLines Function

Explaining the countLines Function

  • Takes as input a string(in this case each string is multiline and represents code)
  • Splits the code using the newline ASCII character as the indicator for each separate line
  • Uses the len function to get the number of lines of the string
  • Casts the result of running the len function as a string and returns it
  • We used three different examples of code, including the countLines function itself

The “Impossible” Proof Attempt

Someone claims they can prove countLines is impossible to implement!

Their Strategy: - Create a program that contradicts itself when counting its own lines - Show this creates an impossible situation - Conclude that countLines cannot exist

Let’s examine this logic…

First, they create countLinesPlus1 that returns n+1 instead of n

WeirdCountlines.py

from countLines import countLines
from countLinesPlus1 import countLinesPlus1

def weirdCountLines(inString):

  if inString == rf('weirdCountLines.py'):
    return countLinesPlus1(inString)

  else:
    return countLines(inString)

The “Contradiction”

What happens when we run: weirdCountLines(rf('weirdCountLines.py'))

  • The program has n lines
  • But it returns n+1 when analyzing itself
  • The output doesn’t match the actual line count!

Question: Does this prove countLines is impossible?

Why This “Proof” Fails

  • Claims:
    • If you feed WeirdCountlines.py into itself, it should be both equal the number of lines from both countlines(n) and countlinesplus1(n+1) at the same time which contradictory. Hence, countlines.py can’t exist.
    • weirdCountLines creates a contradiction when analyzing itself
    • This proves countLines cannot exist
  • Flaw:
    • This is called a liar-paradox.
    • It just assumes based on the code that is made to misbehave on itself, sort of like trickster program.
    • It does not create a contradiction for countlines.py.

countlines is computable

  • countlines is both computable and tractable.
    • We can build a program which can count lines of other programs.
    • We can do it effectively and efficiently.
    • We can do it linear time O(n).

Conclusion

  • countLines is provably computable - we can always count lines efficiently
  • The “impossible” proof fails because it relies on a liar paradox, not genuine contradiction
  • Self-referential trickery ≠ mathematical impossibility
  • This builds intuition for understanding real impossibility results ahead

Key Takeaway: Just because we can create programs that lie about themselves doesn’t mean the underlying computational task is impossible!