Skip to content

JA8. Learning Journal 8

Answer the following questions in your Learning Journal

1. Describe what you did. You need to describe what you did and how you did it

This was the final week of this course; it talked more about limits of computation. I started by reading the materials assigned in the learning guide, then I did the discussion assignment which was about describing the halting problem and provide examples about it.

2. Describe your reactions to what you did

Continuing from the previous week where we divided the problems into classes of P, NP, NP-hard and NP-complete, this week we learned about the halting problem as an example of impossible problems. An impossible problem is a problem that cannot be solved by any algorithm; that is, its solution cannot be computed in a finite number of steps. Examples include the halting problem and the decision problem, or any problem that may involve an infinite loop in its solution (UoPeople, 2025).

3. Describe any feedback you received or any specific interactions you had. Discuss how they were helpful

The discussion assignment asked to describe the halting problem and provide examples about it. I found it interesting to learn how to identify a halting problem and what makes it as such. I chose two examples; first was the Collatz sequence which only halts if the number is 1 or below. The second example was the Busy Beaver problem which is a theoretical problem that asks for the maximum number of steps a Turing machine with a given number of states can take before halting when started on an empty tape.

I was happy in choosing those examples as they are both interesting and relevant to the topic. I also read some interesting responses from my classmates.

4. Describe your feelings and attitudes

I feel that the discussion assignment seemed particularly practical as it presented a real life issue which connects the theory to the real world. However, I think that student should implement the learnings using a programming language to understand them better.

5. Describe what you learned

A decision problem is a problem whose output is a single boolean value: YES or NO. Polynomial time refers to a time complexity of the form O(n^c) for some constant c, where n is the size of the input. Problems are efficient if they can be solved within polynomial time. P problems are those efficient problems that can be solved in polynomial time (Shaffer, 2011).

Verifying a problem solution means that given a solution, it can be checked to determine if it is correct. NP problems are those that could be solved in polynomial time; that is, they are sometimes solvable and sometimes not, but there is no guarantee that they will be. NP problems are non-deterministic problems, meaning they could give different results each time they are run with the same input. NP problems are those that can be verified in polynomial time where the answer is YES (UoPeople, 2025).

NP-hard problems are those that are at least as hard as the hardest problems in NP. They are harder than NP problems; meaning no one has been able to solve them in polynomial time. NP-complete problems are those that are both in NP and NP-Hard; that is, there is no fast solution to them and they may be verifiable or not.

The halting problem is relevant to the design and analysis of algorithms because it highlights the limitations of computation and the inherent complexity of certain problems. It was the driver behind Alan Turing’s work on computability theory, which laid the foundation for modern computer science (Mlo, 2019).

It is important for programmers to be able to recognize an NP-complete or impossible problem so that they don’t unknowingly waste time trying to solve a problem that is unsolvable or unpractical to solve. Understanding the halting problem helps programmers and computer scientists recognize when a problem may not have a solution or when an algorithm may not terminate.

6. What surprised me or caused me to wonder?

I was surprised to learn the halting problem was older than the computer itself. It was first proposed by Alan Turing in 1936, and it is still an open problem today. The halting problem is a decision problem that can be represented in a Turing machine, but it is impossible to solve. It is interesting to see how the theory of computation has evolved over the years, and how it still applies to modern computing.

7. What happened that felt particularly challenging? Why was it challenging to me?

The difference between NP-complete, NP-hard, and impossible problems was a bit confusing at first. The names are super confusing and the texts -we read- confuse the problem and its solution so I got lost between the two. I was able to search more and found that NP-complete problems are those that are both in NP and NP-Hard; that is, there is no fast solution to them and they may be verifiable or not. NP-hard problems are those that are at least as hard as the hardest problems in NP. They are harder than NP problems; meaning no one has been able to solve them in polynomial time. Impossible problems are those that can not be solved at all in any time.

8. What skills and knowledge do I recognize that I am gaining?

I am gaining a better understanding of NP-complete, NP-hard, and impossible problems. As explained earlier, NP-complete problems are sometimes can be solved in polynomial time, but they are always verifiable in polynomial time. NP-hard problems can not be solved or verified in polynomial time, but may be solved in more time. Impossible problems are those that can not be solved at all in any time.

9. What am I realizing about myself as a learner?

I am realizing that I need a systemic method to verify what I am working on. For example, theoretically tackling the halt problem gave me the feeling that I understood everything in the unit. But, as soon as I went to the examples, I had a problem identifying what qualifies as a halting problem and what does not.

10. In what ways am I able to apply the ideas and concepts gained to my own experience?

The skill to spot NP and NP-complete problems as early as possible is very useful. Such problems can not be solved efficiently, and identifying them early on can save time and effort. I also learned that the ability to reduce a problem to another problem is a powerful problem solving technique.

References