<p>A <a href="http://esolangs.org/wiki/Bigot" rel="noreferrer">bigotous program</a> 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 <a href="https://en.wikipedia.org/wiki/Rice%27s_theorem" rel="noreferrer">Rice's theorem</a>.</p>

<p>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.</p>

<p>What are some computational models that <em>do</em> support bigots?</p>

CC BY-SA 3.0
2017-06-08T15:17:55.833Z
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\}$?
Andrej Bauer
CC BY-SA 3.0
2017-06-08T16:14:52.297Z
What a definition, lol, +1
Daniel Apon
CC BY-SA 3.0
2017-06-08T18:20:56.460Z
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.
Daniel Apon
CC BY-SA 3.0
2017-06-08T18:21:56.863Z
(Or, perhaps, that's a decent, early observation: The description length of Barrington's branching programs are longer than their input length -- right?)
Daniel Apon
CC BY-SA 3.0
2017-06-08T18:49:11.030Z
@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?
Andrej Bauer
CC BY-SA 3.0
2017-06-08T18:51:44.670Z
@AndrejBauer Not even standard hyper-computation has such programs.
Christopher King
CC BY-SA 3.0
2017-06-08T18:58:52.657Z
How about infinite-time Turing machines?
Andrej Bauer
CC BY-SA 3.0
2017-06-08T19:02:31.970Z
Ahh-- I was thinking of restricting the computational model, rather than generalizing it (as the question appears to be about). Carry on~
Daniel Apon
CC BY-SA 3.0
2017-06-08T19:03:16.330Z
@DanielApon I'm fine with either direction (ideally, an answer should address both).
Christopher King
CC BY-SA 3.0
2017-06-08T19:06:21.853Z
@AndrejBauer maybe
Christopher King
CC BY-SA 3.0
2017-06-10T22:29:01.450Z
There's a bit of a question what to do with programs that aren't total. That is, what is $L_n$ supposed to be when the $n$-th program diverges on some inputs?
Andrej Bauer
<computability><semantics><decidability>
Which computational models support bigotous programs?
Christopher King
# Which computational models support bigotous programs?

(Asked by: username_0 on 2017-06-08)

A [bigotous program](http://esolangs.org/wiki/Bigot) 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](https://en.wikipedia.org/wiki/Rice%27s_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?

**Tags:** computability, semantics, decidability
> **Comments:**
> **username_1**: 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\}$?  
> **username_2**: What a definition, lol, +1  
> **username_2**: 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.  
> **username_2**: (Or, perhaps, that's a decent, early observation: The description length of Barrington's branching programs are longer than their input length -- right?)  
> **username_1**: @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?  
> **username_0**: @AndrejBauer Not even standard hyper-computation has such programs.  
> **username_1**: How about infinite-time Turing machines?  
> **username_2**: Ahh-- I was thinking of restricting the computational model, rather than generalizing it (as the question appears to be about). Carry on~  
> **username_0**: @DanielApon I'm fine with either direction (ideally, an answer should address both).  
> **username_0**: @AndrejBauer maybe  
> **username_1**: There's a bit of a question what to do with programs that aren't total. That is, what is $L_n$ supposed to be when the $n$-th program diverges on some inputs?  

---

## 0 answers

