Dev Blog

./dev



Original heme by orderedlist (CC-BY-SA)


Where applicable, all content is licensed under a CC-BY-SA.
Creative Commons License

Halting Problem

The Halting Problem asks whether there exists a program that takes other programs as input and determines whether they loop forever or halt.

Assume such a program exists and call it HP.

The program HP(P,X) assumes:

Though a bit far afield from the current topic, there also needs to be constraints on the time it takes to access distant memory so as not to 'hide' computation in memory access. For example, assuming memory is a linear tape and the time to reach a distance, d, from the current location takes time proportional to d.

Consider the program SPITE:

SPITE(P) {

  if (HP(P,P) reports P halts with P as input) {
    while (true) {} // loop forever
  }

  else if (HP(P,P) reports P loops forever with P as input) {
    halt // return
  }

}

When we run SPITE(SPITE) (SPITE with itself as input), there are two cases:

No matter the path we take, we get a contradiction, proving the impossibility of HP existing with our given assumptions.

2018-06-13