Analysis of Algorithms

University Of the people

Course number: CS 3304 01

Instructor: Ahmad AlRababaa

Due: Friday 28th May , 2025

 Learning Journal Unit 8

This week, I focused on Unit 8’s exploration of NP-completeness

and impossible problems, especially the halting problem. To begin, I
read the Learning Guide and the assigned textbook chapters on
computational complexity and decidability. I paid particular
attention to the sections that explain reductions (transforming one
problem into another) and the formal proof that the halting problem
is undecidable. After reading, I drafted my discussion post on the
halting problem, articulating why a universal “halts checker” cannot
exist. In crafting that discussion entry, I restated Turing’s
diagonalization argument in my own words, described why no
algorithm can decide termination for every possible program and
input, and offered concrete examples (such as a program that loops
forever versus one that decrements a counter until zero). Once I
submitted my initial post, I reviewed my classmates’ comments and
responded to two peers, clarifying points about how reductions work
and discussing how the halting problem influences modern static-
analysis tools.

During this process, I felt a mixture of excitement and mild

apprehension. I was excited because I enjoy theoretical computer
science, and the elegance of Turing’s proof never ceases to
fascinate me. However, I also felt a bit intimidated by the formalism
surrounding NP-completeness and undecidability. I wondered if I had
fully grasped the nuances especially when my classmate asked how
the halting problem relates to NP-hard problems, since NP-
completeness relies on polynomial‐time reductions, whereas the
halting problem is about decidability itself. Initially, that question
caused me to pause and revisit the Learning Guide, comparing the
definitions of “undecidable” versus “NP-hard.” Revisiting the
material helped me realize that NP-hardness is a statement about
the relative difficulty of decision problems within the class of
decidable problems, while the halting problem transcends those
classes entirely by being undecidable. When I clarified this in my
reply, my peer thanked me for distinguishing the two concepts, and
that positive feedback boosted my confidence.

One challenge I encountered was condensing the proof of the

halting problem’s undecidability into a brief, discussion‐forum‐
friendly format. I wanted to include enough detail to show I
understood the paradoxical “machine that runs forever if and only if
it halts” construction, but I also needed to keep my post to a
reasonable length. Balancing depth with brevity felt like walking a
tightrope. Ultimately, I decided to provide a concise description of
the diagonalization step enough so that a reader could follow the
logic but included references to Sipser’s textbook for those who
wanted the full technical details. While writing that post, I realized
I’m improving my ability to communicate complex theoretical ideas
to a broader audience, not just to fellow theory‐major students but
also to those who might be new to formal proofs.

Reflecting on my learning approach, I see that I’m becoming more

comfortable with self‐directed reading. In prior units, I sometimes
felt overwhelmed by the volume of formal definitions and wondered
if I was “getting it.” This week, I took more time to pause after each
section of the readings, summarize the key points in my own words,
and jot down any questions. For example, when I first read about
reductions how to show that SAT reduces to 3‐SAT by constructing a
new Boolean formula I paused to work through a simple example.
That hands‐on practice helped cement my understanding. As a
result, I felt less anxious when later writing about why the halting
problem cannot reduce to any decidable problem: I could articulate
that if we could reduce the halting problem to a decidable problem,
we would contradict Turing’s theorem.

Throughout this week, I also noticed how my attitude toward “hard”

problems is evolving. At first, I equated “hard” with “impossible,”
assuming that NP-hard problems are just as hopeless as
undecidable ones. But by contrasting NP-completeness where
problems are believed to have no known polynomial-time solution
with the halting problem where no algorithmic solution exists at all I
learned to draw a sharper distinction between “practically
intractable” and “provably unsolvable.” That distinction surprised
me and caused me to wonder: how often do practitioners conflate
intractability with undecidability? I realize now that it’s crucial to
distinguish if a problem is in PSPACE, NP, or is outright undecidable,
because that determines whether we can hope for heuristics,
approximate algorithms, or if we must accept that no algorithm at
all will ever solve the general case.

In terms of feedback, my instructor commented that my discussion

post demonstrated a solid grasp of the diagonalization technique
but encouraged me to expand more on how this theoretical limit
influences real‐world programming tools. I took that to heart by
adding in my peer‐reply discussions about why compilers and static
analyzers can never perfectly prove termination, and why they rely
on conservative approximations (e.g., loop invariants or ranking
functions). That interaction helped me connect the abstract proof to
concrete software‐engineering practices, making the material feel
more relevant.
Emotionally, I felt a sense of pride as I saw myself articulating these
concepts clearly. I also felt inquisitive: what other undecidable
problems exist beyond the halting problem? I recall briefly reading
about the Post Correspondence Problem in the textbook and
wondering if I should explore that topic in the future. I recognized
that I’m gaining both theoretical knowledge (understanding
reductions, NP‐completeness, and undecidability) and soft skills
(explaining complex ideas succinctly, engaging in academic
dialogue).

As a learner, I’m realizing that I thrive when I alternate between

deep reading, active summarization, and peer discussion. I’m more
aware of my tendency to skim formal proofs, so I consciously slowed
down this week. In doing so, I noticed details I overlooked before—
such as the precise role of self‐reference in Turing’s argument.
Finally, I can already see applications of these concepts in my own
coding experience. When I write recursive functions or intricate
loops, I now pay closer attention to termination arguments. I ask
myself: “Is there any input for which this routine might not halt? Can
I define a well‐founded measure that strictly decreases each
iteration?” These questions used to feel abstract, but after studying
the halting problem, I appreciate why such checks are not just good
practice but necessary, since we know no automated tool can do
this perfectly for us.

Finally, Unit 8’s focus on impossible problems and NP‐completeness

challenged me to think rigorously about what can and cannot be
computed. I practiced summarizing proofs, participated in
substantive discussions, and confronted my initial confusion around
“hard” versus “undecidable.” Through the feedback I received and
my own reflective pauses, I solidified my understanding of the
halting problem’s significance in algorithm design and analysis. I
feel more confident in my ability to tackle future theoretical topics
and I am developing a healthy respect for the boundaries of
computability that inform every programmer’s work.