Determines whether two Predicate<Predicate<Integer>>s are equivalent. Really.

BitsPredicateEquivalence

// An infinite bit-string.
public interface Bits {
  // requires n >= 0
  boolean bit(int n);
}

// Determines the equivalence of predicates over infinite-bit-strings.
// Requires that the given predicates halt for all inputs.
public final class BitsPredicateEquivalence extends Equivalence<Predicate<Bits>> {

  @Override
  public boolean doEquivalent(final Predicate<Bits> pred1, final Predicate<Bits> pred2) {
    final Predicate<Bits> disagree = new Predicate<Bits>() {
      @Override
      public boolean apply(Bits input) {
        return pred1.apply(input) != pred2.apply(input);
      }
    };

    return !disagree.apply(new SearchBits(disagree, new HashMap<Integer, Boolean>()));
  }

  @Override
  protected int doHash(Predicate<Bits> t) {
    // What? Technically correct is the best kind of correct.
    return 0;
  }

  // An adversarial infinite bit-string, that brute-force searches for a bit-string that a predicate accepts by
  // triggering alternate searches then using the ones that worked.
  //
  // The search is guaranteed to terminate because the predicate can't depend on more than a finite number
  // of bits (otherwise there would be cases where it failed to accept or reject a bit string due to not halting).
  //
  // The performance is a terrible O(n 2^n) where n is the maximum number of bits that the predicate can read.
  // But that's still amazing given what's being done!
  private static final class SearchBits implements Bits {
    private final Predicate<Bits> predicate;
    private final HashMap<Integer, Boolean> history;

    public SearchBits(Predicate<Bits> predicate, HashMap<Integer, Boolean> history) {
      this.predicate = predicate;
      this.history = history;
    }

    @Override
    public boolean bit(int n) {
      if (!history.containsKey(n)) {
        HashMap<Integer, Boolean> future = new HashMap<>(history);
        future.put(n, true);
        boolean matchedWhenTrue = predicate.apply(new SearchBits(predicate, future));

        // If true worked, use it. Otherwise we'll try false.
        history.put(n, matchedWhenTrue);
      }

      return history.get(n);
    }
  }
}