4 ms·

cough Hypercomputation cough

• IngoBlechschmid 8y ago
  Hypercomputation is a fascinating concept; I particularly like infinite-time Turing machines, which can continue computing "at the end of time" (day ω), at the day after that (ω + 1), the day after that (ω + 2), at the second end of time (day ω ⋅ 2), the day after that (day ω ⋅ 2 + 1), and so on. Infinite-time Turing machines can readily solve the halting problem for ordinary Turing machines, but (by the same proof) not for themselves. The theory of infinite-time Turing machines is in some regards parallel to the theory of ordinary Turing machines and in others quite different. I particularly enjoy the Lost Melody Theorem: There is a specific infinitely long 0/1 sequence for which (a) it's possible to devise an infinite-time Turing machine which will correctly detect whether that 0/1 sequence is written on the input tape, but (b) there is no infinite-time Turing machine which will, starting on an empty tape, write out that 0/1 sequence to the output tape. It's like when you would recognize a song but cannot sing it. Some details are here: https://rawgit.com/iblech/mathezirkel-kurs/master/superturingmaschinen/slides-warwick2017.pdf https://rawgit.com/iblech/mathezirkel-kurs/master/superturin...