[scatters]

> What if we propose the existence an "imaginary" algorithm (call it omega, if you like) that can decide the halting problem?

This is called an oracle (https://en.wikipedia.org/wiki/Oracle_machine). We can posit oracles for solving computable problems in constant time (e.g. factoring the product of two arbitrarily large primes) as well as for solving uncomputable problems (e.g. halting problems).

Oracles are a great tool for studying complexity and computability, since oracle machines have their own complexity and computability limits; an oracle machine for the halting problem can determine whether a simple Turing machine will halt, but cannot determine whether it itself will halt (this is called a Turing jump). Thus oracle machines for halting problems form a class hierarchy, which Post's theorem shows is precisely the arithmetic hierarchy.