Can such machines be built in practice?
Yes. By "machine", Schmidhuber just means "computer program".
Are they at least feasible in our Universe?
Not in their current form -- the algorithms are too inefficient.
From a ten thousand meter perspective, Jürgen Schmidhuber (and former students, like Marcus Hutter) have been investigating the idea of combining Levin search with Bayesian reasoning to work out algorithms for general problem-solving.
The basic idea behind Levin search is that it's possible to use dovetailing and Goedel codes to give a single algorithm which is, up to constant factors, optimal. Loosely, you fix a Godel encoding of programs, and then run a Turing machine that runs the $n$-th program once every $2^{n}$ steps. This means that if the $n$-th program is optimal for some problem, then Levin search will "only" be a constant factor of $2^n$ times slower.
They have done a fair amount of work on making the constant factors less stupendously, horrifically awful, and are optimistic that this kind of scheme can work in practice. I am (based on my experience in automated theorem proving) very skeptical, since good data structures are critical to theorem proving, and Goedel encodings are terrible data structures.
But you don't know it can't work until you try to make it work! After all, we already live in a world where people solve problems by reduction to SAT.