Pointwise running-time domination problem
ID: pointwise-running-time-domination-problem
Give a nonhalting Turing machine computation halting time infinity. The formal language of pairs satisfying the displayed inequality is a co-recursively enumerable language but is not a recursively enumerable language. A violation has a finite witness: has halted on some input after moves while has not halted by that time. For the other direction, reduce non-halting by making simulate a fixed computation on every input and making run forever. The pair satisfies domination exactly when the fixed computation never halts. The convention is essential to this many-one reduction.
New to topics? Read the docs here!