Undecidable Problems

popcorn/homework hacks

• 3 min read

POPCORN HACKS

Hack 1

Nodes (Vertices) → Cities

Edges → Roads between cities

Weights → Distance or cost of travel

Draw a simple 5-city graph on the board and discuss possible routes.

We can represent cities and paths as a graph by using nodes (vertices) to represent the cities, edges to represent the roads connecting the cities, and weights on the edges to represent the distance or cost of traveling between them.

Hack 2

#r Greedy Coin Change Code
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

reflection: Changing the coin order to start with the smallest coins made the algorithm much less efficient because it used way more coins to make the same amount. This shows that greedy algorithms can work well only if the choices are ordered wisely.

Hack 3

The second code (num = 1; while num != 0) is an undecidable problem because the number num keeps increasing forever it will never reach 0, so the program will never halt. There’s no way to know ahead of time without running it forever, which matches the idea of the Halting Problem.

Hack 4

#1 An algorithm might solve some instances of an undecidable problem but cannot guarantee a correct answer for every possible case. That’s what makes it undecidable.

#2 Even though a problem is undecidable overall, a programmer can still create an algorithm that works for many cases, but it won’t work for every case — and there’s no way to fix that completely. So not all problems have an algorithmn that works for them, making then undecidable problems!

HOMEWORK HACKS

Hack 1

Q1: In which of the configurations is it possible to have redundant routing between devices Q and V?

A) Configuration 1 only

Q2: In configuration I, what is the minimum number of connections that must be broken or removed before device T can no longer communicate with device U?

B) 2

Hack 2

Changing the order of coins affected how efficiently the greedy algorithm worked, using the largest coins first resulted in fewer coins overall. Greedy algorithms work well when local choices lead to an optimal global result, but they can fail when short-term decisions don’t lead to the best overall solution. By switching the coin order, I saw that greedy methods aren’t always perfect and need smart design to be effective.

Hack 3

PART 1

“Is this number divisible by 2?” = decidable, with the use of a module operater (DECIDABLE)

“Will this program stop or run forever?” = This is “the Halting Problem” no universal algorithm solve it (UNDECIDABLE)

“Does this sentence contain the word ‘banana’?” = Algorithm can scan and output if it does/does not exsist (DECIDABLE)

“Will this AI ever become sentient?” = There’s no known algorithm that can always predict AI sentience. (UNDECIDABLE)

PART 2

Algorithm 1: Decidable

Algorithm 2: Undecidable

PART 3

Waiting to see if it will ever rain on a cloudy day — you can’t know for sure unless you wait and watch the entire day, which mirrors how some outcomes are unknowable without living through the full experience/having hindsight