if a predicate depends on finitely many bits then you can exhaustively check whether it is total by enumerating all of it's possible inputs