Decidable Problem

A decidable problem is one that we can come to a yes/no answer given any input. An examle would be given a number determine if it is divisible by 3. We know that the algorithm below would provide the correct ouput every time.

PRODECURE divisbleByThree(num)
    IF (num MOD 3 = 0) 
        RETURN true
    ELSE
        RETURN false

Undecidable Problem

Halting Problem

The halting problem is defined as: Given an arbitrary computer program with given inputs will the program stop or will it run forever?

Undecidable Problems

A problem where an algorithm cannot make a correct yes/no answer every time.

One way would be to test for an ending, but what if that ending is not easily found? What if it takes an unreasonable amount of time to find the ending? Is that because there is an ending or does one not exist?

You see where the problem comes in? This is an undecidable problem – there is no algorithm which can always produce a yes/no answer for every input of the problem.

Halting Problem in Computers Where may we have seen this in computers today? When a website or program takes too long to load it. It may never load, or it may just be taking a long time. Either way, after a certain time the computer decides the program should be stopped.

Popcorn Hack #1

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

Popcorn Hack #2

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

Scenarios of Undecidable Problems in Computing

  1. Infinite Loop in Program Execution:
    • When a program enters an infinite loop, it becomes undecidable whether it will eventually terminate or run indefinitely.
  2. Complex Conditional Statements:
    • Programs with intricate conditional statements or complex control flow may pose undecidable scenarios, making it challenging to determine their termination.
  3. Non-Terminating Recursive Functions:
    • Recursive functions that do not have a base case or have poorly defined termination conditions can result in undecidability regarding their halting behavior.
  4. Unknown Input Space Size:
    • In cases where the size of the input space is unknown or unbounded, it becomes difficult to ascertain if a program will halt for all possible inputs.
  5. Multithreading and Concurrency:
    • Undecidability may arise in concurrent programs where multiple threads interact, introducing intricate synchronization and communication challenges.

Popcorn Hack 3

An algorithm exists that can always produce a yes/no answer for the halting problem. (True/False)

  • false

Homework Question

Research and explain how modern systems or browsers deal with the aspects of the halting problem when a program takes too long to load. Provide examples of mechanisms or strategies implemented in real-world scenarios to manage unresponsive programs or prolonged loading times.

Modern systems and browsers employ various mechanisms and strategies to address the challenges posed by the halting problem when a program takes too long to load. One common approach is the use of timeouts. Timeouts are predetermined durations set by the system or browser, after which they assume that the program has taken too long to respond. When a timeout expires, the system or browser can take actions such as displaying an error message, terminating the program, or triggering a retry. Another technique is asynchronous loading. This involves breaking down the program or webpage into smaller tasks and loading them independently. By doing so, the system or browser can display partial content or interactive elements even if other parts are still loading. Caching is another strategy used to improve loading times. Browsers can store frequently accessed resources locally, allowing subsequent requests to be served more quickly. Additionally, preloading and prefetching are techniques where the system or browser anticipates user actions and proactively loads resources in advance to reduce perceived loading times. These mechanisms, along with others, are implemented in real-world scenarios to manage unresponsive programs or prolonged loading times, thereby enhancing user experience and mitigating the impact of the halting problem.