5
$\begingroup$

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?

$\endgroup$
  • 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$ – Andrej Bauer Jun 8 '17 at 15:17
  • 1
    $\begingroup$ What a definition, lol, +1 $\endgroup$ – Daniel Apon Jun 8 '17 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$ – Daniel Apon Jun 8 '17 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$ – Andrej Bauer Jun 8 '17 at 18:49
  • 1
    $\begingroup$ @DanielApon I'm fine with either direction (ideally, an answer should address both). $\endgroup$ – PyRulez Jun 8 '17 at 19:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.