Week 11

    This week, we talked about the computability of programs. Some programs just cannot be written as any sort of algorithm, such as a program that checks whether another program halts. There is no reasonable computational model that can represent this impossible halt function. Actually running the program to see if it halts is not a reasonable solution to the halting problem because it could take years for a program to halt, and at some point it would be hard to tell whether a computer never halts, or just won't halt for at least 3 million years.
    But what counts as a 'reasonable computational model'? If there was a supercomputer with enough processing power to simulate the entire universe and account for every particle in existence, surely it would be able to compute anything. So if you run that program that either halts in 3 million years or goes on forever, the supercomputer would probably know the answer before you even run the program.
    Now, this theoretical supercomputer is itself unreasonable. However, lets say that the universe will last for 100 trillion years, when all the particles universe will drift too far apart from each other to interact. Assuming humans could survive this long, we could say that any program that halts after 100 trillion years or more is for all intents and purposes, a program that never halts. So if we get a supercomputer that can run this program fast enough and check whether it will halt within 100 trillion years, then we get a useful answer in a reasonable amount of time by just running the program. Or we could time travel to the end of the universe and see if the program has halted.
    The point is, while it may be impossible to compute some programs in the traditional sense, with enough processing power or time travel, we can still get a useful answer. Which is why I am going to solve the halting problem by creating a computer that can accelerate time and check every single program in existence to see whether or not they halt. Shouldn't be too hard.