This might combine well with the setup I thought of for studying bounded rationality / approximate utility maximizers. Namely, the setup is like that for UDT, but your algorithm has to pay 1 utilon for every call to its halting oracle. What algorithm might you use for this game?

(I find it easier to imagine that the algorithm is proving things only about the utility of the action not counting the computational costs.)