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!