Ahaan

Nighthawk PagesBig Idea 1 JourneySearchAbout Me!BlogsReadmeView on GitHub

Undecidable Problems and Heuristics

• 3 min read

Undecidable Problems

Popcorn Hack 1

Q: An algorithm can be used to solve an undecidable problem. (True/False)

A: False
An undecidable problem has no algorithm that can solve all cases correctly. Partial solutions may exist, but no universal algorithm.

Popcorn Hack 2

Q: If a programmer encounters an undecidable problem, they can just use an algorithm that works most of the time. (True/False)

A: True
While no algorithm can solve all cases, heuristics or partial solutions often work for practical instances.

Popcorn Hack 3

Q: Which of the following options is not an example of an undecidable problem?

A. Halting Problem
B. The Collatz Conjecture
C. Rice’s Theorem
D. Bubble sorting

A: D. Bubble sorting
Bubble sorting is a decidable problem — there is always a correct and terminating algorithm for sorting lists.

Undecidable Problems Homework

Question:
Investigate how modern operating systems and browsers handle infinite loops or excessively long-running scripts. What mechanisms detect and mitigate such issues? Give real-world examples.

Operating Systems

  • Watchdog Timers:
    Hardware or OS-level timers detect stuck programs and force resets or shutdowns.

  • Process Killers:
    Users or the OS can terminate processes using:
    • Windows: End Task via Task Manager.
    • Linux/macOS: kill -9 PID.
  • Real-World Example:
    • Windows: Program Not Responding → End Task.
    • Linux: kill -9 1234 (PID).

Web Browsers

  • Script Timeout Detection:
    Browsers auto-detect long-running JavaScript and stop execution to prevent freezing.

  • Error Messages:
    • Chrome: “Page Unresponsive — Wait or Exit”
    • Firefox: “A script on this page may be busy…“
  • Built-in Timeouts:
    JavaScript and WebAssembly have execution time limits; exceeded scripts are paused or killed.

Real-World Examples

  1. Chrome:
    Infinite loop → “Page Unresponsive” popup appears.

  2. Firefox:
    Long-running script → “A script on this page may be busy” alert.

  3. OS Level:
    Applications stuck in infinite loops show Not Responding. Users can force quit.

Summary:
Modern OS and browsers prevent infinite loops from freezing systems using timers, watchdogs, kill switches, and timeout-based detection. These tools protect users from non-terminating code.

Heuristics

Popcorn Hack #1

Q: True or False:
In a directed graph, an edge from node A to node B implies that there is always a corresponding edge from node B to node A.

A: False

In directed graphs, edges have direction. An edge from A to B does not guarantee an edge from B to A.

Popcorn Hack #2

Q: True or False:
Heuristics always provide faster solutions than exact algorithms, but they may sacrifice accuracy for speed.

A: True

Heuristics trade guaranteed accuracy for speed and efficiency — especially useful for hard optimization problems.

Popcorn Hack #3

Q: True or False:
While heuristic algorithms like the Nearest Neighbor algorithm can significantly reduce the computational time for TSP, they can never guarantee an optimal solution, and the gap between the heuristic solution and the optimal solution can grow exponentially as the number of cities increases.

A: True

Heuristics help compute solutions faster but don’t always reach the perfect answer, especially as problem size grows.

Homework: Graphs & Social Networks

Q: Explore the concept of “Social Network Analysis” and explain how graphs are used in analyzing social media platforms.

How are users and relationships represented?

  • Nodes (Vertices): Represent individual users.
  • Edges: Represent connections like friendships, follows, or interactions.

Real-World Example:

Platform: Facebook

  • Users are nodes.
  • Friendships are edges (undirected).
    Graph theory helps analyze:
  • Friend clusters.
  • Influential nodes.
  • Network growth.
Scroll to top