Skip to content

Instantly share code, notes, and snippets.

Created November 12, 2014 03:48
What would you like to do?
Determines whether two Predicate<Predicate<Integer>>s are equivalent. Really.
// 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>> {
public boolean doEquivalent(final Predicate<Bits> pred1, final Predicate<Bits> pred2) {
final Predicate<Bits> disagree = new Predicate<Bits>() {
public boolean apply(Bits input) {
return pred1.apply(input) != pred2.apply(input);
return !disagree.apply(new SearchBits(disagree, new HashMap<Integer, Boolean>()));
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;
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);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment