Formalizing or describing something is not the same as "deducing a boolean value". But I can ask GNU Maxima to give me a list of all numbers that satisfy the eq

Formalizing or describing something is not the same as "deducing a boolean value". But I can ask GNU Maxima to give me a list of all numbers that satisfy the equation x+1=x-1, and it will happily tell me that there is no such number. Maxima doesn't support self-referential propositional logic, but a solver that can identify that no truth value can support "this sentence is false" doesn't need to do anything more mystical than test both cases - no "polynomial search algorithm" required. You are suggesting that "human consciousness" is a separate, ineffable thing from a "purely logical system", but I don't see any reason a computer couldn't do what your brain is doing. You can't tell me the truth value of the sentence either.