Undecideable Programs

Popcorn Hack 1

Which program is undecidable?

  • The second program is undecideable as the program continues increasing forever and does not terminate and continues to infinity.

Popcorn Hack 2

  1. True or False. An algorithm can be used to solve an undecideable problem.
    • False. An algorithm cannot be used to solve an undecidable problem because, by definition, there is no algorithm that can provide a correct yes-or-no output for all possible inputs. Undecidable problems do not have a universal procedure that works for every case, so any algorithm will fail to correctly solve the problem for some inputs.
  2. If a programmer encounters an undecideable problem,they can just use an algorithm that works most of the time.
    • False. While a programmer might attempt to create an algorithm that works for many inputs, the problem remains undecidable because there will always be some inputs for which the algorithm cannot give a guaranteed correct answer. According to the College Board, a problem is only decidable if there exists an algorithm that works correctly for all inputs. An algorithm that works most of the time does not make an undecidable problem decidable.

Graphs

Popcorn Hack 1

Draw a 5 city graph Image

Heurisitics

Popcorn Hack 1 - Greedy Algorithm

def greedy_coin_change(amount, coins=[1, 5, 10, 25]):
    change = []
    for coin in coins:
        while amount >= coin:
            amount -= coin
            change.append(coin)
    return change

# Example usage:
amount = 63
result = greedy_coin_change(amount)
print(f"Change for {amount}¢: {result}")
print(f"Total coins used: {len(result)}")

Change for 63¢: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
Total coins used: 63

The algorithm always picks the largest coin possible first, reducing the amount until it reaches 0.

Default Coin Order (Greedy):

coins = [25, 10, 5, 1]  # largest to smallest

It works well for U.S. coins because the greedy choice gives the fewest coins most of the time.

Flipped

Change the coin order to:

coins = [1, 5, 10, 25]  # smallest to largest

Now the algorithm uses small coins first, which means:

  • More total coins
  • Slower to reach the goal

Comparison: amount = 63

With [25, 10, 5, 1]:

  • Greedy picks: 25, 25, 10, 1, 1, 1
  • Total coins = 6

With [1, 5, 10, 25]:

  • Picks: sixty-three 1¢ coins

  • Total coins = 63

Reflection: Is the Greedy Algorithm Perfect?

  • Efficient for some coin systems like U.S. coins
  • Not perfect if the coin system is weird (e.g., [9, 6, 1])
  • Sometimes you need dynamic programming or exhaustive search for perfect solutions

Homework Hacks

Undecidable Problems

Part 1: Identify the Problem Type

1. “Is this number divisible by 2?”
➤ Decidable
You can write a clear algorithm: if the number mod 2 equals 0, return yes. It always gives a correct answer.

2. “Will this program stop or run forever?”
➤ Undecidable
This is the famous Halting Problem. No algorithm can guarantee a correct yes/no answer for all programs.

3. “Does this sentence contain the word ‘banana’?”
➤ Decidable
You can scan the sentence word by word and check if “banana” is present. The process always ends with a definite answer.

4. “Will this AI ever become sentient?”
➤ Undecidable
There’s no algorithm that can determine future sentience for all possible AI systems—this depends on unknown and unpredictable factors.

Part 2: Algorithm Detective

Algorithm A:

Step 1: Input a number
Step 2: If the number is even, say “Yes.” If not, say “No.”
➤ Decidable
This algorithm always finishes and gives a correct yes/no output. It’s a simple check using modulus.

Algorithm B:

Step 1: Input any program
Step 2: Predict if it will ever stop running
Step 3: Output “Yes” if it will stop, “No” if it will run forever
➤ Undecidable
This is trying to solve the Halting Problem. You cannot guarantee a correct answer for every possible input program.

Part 3: Real-Life Connection

Example: A real-life undecidable situation is like opening a mysterious gift box without instructions. You won’t know what’s inside unless you actually try to open it. Just like with undecidable problems, you can’t predict the result without going through the full process. And sometimes, you might never get an answer at all.

Graphs

Q1 - B: Redundant routing between devices Q and V is possible in Configuration II. In Configuration II, there are multiple paths available for communication between Q and V, allowing for redundancy. Configuration I only has a single path, so it doesn’t offer redundancy.

Q2 - B: In Configuration I, if two connections are broken or removed, specifically the connections between devices P-Q and Q-R, then device T will no longer be able to communicate with device U.

Heurisitics

  1. How did changing the order of coins affect the result? Changing the coin order from largest-to-smallest to smallest-to-largest made the algorithm much less efficient. Instead of picking the biggest coin available, the algorithm kept adding small coins, which increased the total number used and slowed down the process.

  2. Which algorithm used fewer coins? The original greedy algorithm with coins in descending order used fewer coins. This is because it prioritized the highest possible value at each step, which reduced the number of total coins needed to reach the amount.

  3. Where might greedy algorithms work well? Where might they fail? Greedy algorithms work well when the problem’s structure allows local decisions to lead to a global best outcome—like U.S. coin denominations. However, they can fail when a short-term choice prevents the best overall result, such as in certain custom coin systems or in complex pathfinding problems.

  4. What is one thing you changed, and what did it show you? I changed the order of the coin values from [25, 10, 5, 1] to [1, 5, 10, 25] to reverse the greedy strategy. This showed that the same algorithm can behave completely differently based on input setup, and that heuristics aren’t guaranteed to be efficient without the right conditions.