A bigotous program is a program which decides if its input is semantically equivalent to itself. Of course, this is impossible in a Turing complete language due to Rice's theorem.

In fact, its pretty hard to find any computational model that supports such a program. Indeed, even extending a computational model with the ability to write bigots often results in contradictions.

What are some computational models that do support bigots?

  • 3
    $\begingroup$ I think it would be useful to write down a formal definition. If $L_n$ is the language recognized by $n$-th program (under some reasonable coding), is a bigot a (code of a) program $b$ such that $L_b = \{ n \in \mathbb{N} \mid L_b = L_n\}$? $\endgroup$ Jun 8, 2017 at 15:17
  • 1
    $\begingroup$ What a definition, lol, +1 $\endgroup$ Jun 8, 2017 at 16:14
  • $\begingroup$ Even if you restrict to programs/functions computable within $\mathsf{NC}^1,$ as represented by the class of outputs of Barrington's transformation to 0/1-valued matrix branching programs (of a given program size and input size).. it's still interesting. No need to push all the way up to $\mathsf{P}$ to find a good question here. $\endgroup$ Jun 8, 2017 at 18:20
  • 1
    $\begingroup$ @DanielApon: What are you talking about? It seems like a legit definition to me, albeit a bit weird. Also, what do complexity classes have to do with anything here? Isn't this a question about (hyper)computation? $\endgroup$ Jun 8, 2017 at 18:49
  • 1
    $\begingroup$ @DanielApon I'm fine with either direction (ideally, an answer should address both). $\endgroup$ Jun 8, 2017 at 19:03


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.