Search code examples
universalturing-machines

Running a UTM on itself and it's description

What happens when a UTM U is run on itself and it's description? does it reject, accept or loop?

Solution

  • The input to a universal TM usually consists of two parts:

    • a description of the TM to simulate
    • the input on which the TM should be simulated

    So when your U is run on its own description only, the input is incomplete and will be rejected. Or it might be interpreted as the emptyy word as input; but this is not a TM description and thus will be rejected, too.