Cool Logic

Jȩdrek Kołodziejski (ILLC)

Computing the Uncomputable: hypercomputation in time loops

November 18th at 17:30, in F1.15

Alan Turing famously solved the halting problem with a negative answer: there is no procedure to decide whether any given algorithm will halt or continue running forever. That sounds like a challenge. This Friday we are going to try the impossible—seeing how time loops could allow us to decide the halting problem. We will also say why finite memory is actually enough to do that, and why even hard randomness cannot stop us. Challenge accepted.