Against eating only dead animals

I try to spare sometime to study human food to figure out what I should and should not eat and make conscious choice about it. Why? Because I think I am privileged enough to do so; I have more options than other people and hence I am responsible of making the best choice out of several options that I have.

So, I do not like the idea of killing animals. This is one of the reasons for having less meat consumption. There are of course other reasons for it such as CO2 emission for processing meat in large scale.

Anyway, I want to focus on not killing animals now. One way to get away from killing is to eat the dead one already. But I am pretty sure this is not really a good idea because otherwise this beautiful idea would have worked out. And I am happy enough with the answer from Simon Bridge in an online forum.

I copy his answer below.

Most of the animals we eat are dead at the time of eating/cooking. “Aged” meat can be dead for quite a while. The exceptions iirc are some seafood. Oysters are traditionally consumed alive while lobsters are traditionally killed by plunging into boiling water as the first stage in cooking. That sort of thing.

Your father is talking about finding an already-dead animal, taking it home and cooking it. The trouble with scavenged prey is that you don’t know the circumstances that it died in – when we kill an animal we have some (with modern farming: lots of) control over the condition of the animal when it is killed. We also have certain knowledge of what it died of. Imagine an animal dies from disease, or from poisoning – is it a good idea to eat it?

Similarly – what sort of organism has taken up in the carcass while it was lying there?

It is technically possible to overcome objections by being careful in selecting the found-meat, as well as preparing it. .e. maybe you saw the animal keel over right in front of you? However, the risks are higher.

As for this approach to obtaining meat as an alternative to killing, you should be able to follow why it is a bad idea institutionally to wait around for an animal to die by itself before processing it for food. i.e. it won’t be in the farmer’s interest to keep the animal in good health.

However, I understand that it is legal in some US States to eat roadkill. Presumably it is not legal to serve it in restaurants though.


It is interesting how there are some exceptions indeed such as seafood and roadkill. I will look for more info later when I have more time. Moreover, since it is difficult to institutionalize this idea, then if I want to survive with this way of obtaining meat, I need to resolve a lot of technical difficulties in recognizing edible dead meat in the wild.


The different forms of quantum computing skepticism

Windows On Theory

(see also pdf version)

Quantum computing is one of the most exciting developments of computer science in the last decades. But this concept is not without its critics, often known as “quantum computing skeptics” or “skeptics” for short. The debate on quantum computing can sometimes confuse the physical and mathematical aspects of this question, and so in this essay I try to clarify those. Following Impagliazzo’s classic essay, I will give names to scenarios or “potential worlds” in which certain physical or mathematical conditions apply.

Potential worlds

Superiorita is the world where it is feasible to build scalable quantum computers, and these computers have exponential advantage over classical computers. That is, in superiorita there is no fundamental physical roadblock to building large quantum computers, and hence the class BQP is a good model of computation that is physically realizable. More precisely, in superioriata the amount of resources (think…

View original post 2,547 more words

Non-deterministic version of accepting and deciding

{\bf NP} is the class of languages that can be decided in polynomial time by a non-deterministic Turing Machine. Now let {\bf NP}' be the class of languages that can be recognized in polynomial time by a non-deterministic Turing machine.

We can ask the same question: Is {\bf NP}={\bf NP}'?

Theorem. {\bf NP}={\bf NP}'.

The proof is almost the same, except that we use non-deterministic Turing Machine, instead of deterministic one. For completeness of the detail, I will write the proof.

Proof. Clearly, {\bf NP} \subseteq {\bf NP}'. Now, let L \in {\bf NP}'. Then there exists a non-deterministic Turing Machine that will accept x \in L in p(n) time, for some polynomial p. Now, we construct a non-deterministic Turing Machine M' that will decide L in polynomial time. Let M' on input x runs a simulation of M(x) in p(n) time. If it halts and ACCEPT, then M' also accepts. Otherwise, REJECT. \square

Still, the proof is non-constructive.

Non-constructive proof in complexity

Let {\bf P} be a class of languages that can be decided in polynomial time by a deterministic Turing Machine. Let {\bf P}' be a class of languages that can be accepted (recognized) in polynomial time by a deterministic Turing Machine.

Theorem. {\bf P}={\bf P}'.

This theorem appears in CLRS book. The proof is non-constructive, roughly as follows.

Proof. It is true that {\bf P} \subseteq {\bf P}' because if it can be decided, then it can be recognized. To prove {\bf P}' \subseteq {\bf P}, let L \in {\bf P}'. Because it can be recognized in polynomial time, then there is a polynomial p(n) such that L can be recognized by a Turing Machine M in p(n) time for input x of length |x|=n. We now construct a polynomial-time deterministic Turing Machine M' that decides L. Let M' is a Turing Machine with input x simulates M(x) up to p(n) time. If it halts and ACCEPT, then M' also ACCEPT. Otherwise, simply REJECT. \square

The main idea of the proof is that if an input x is in L, then the Turing Machine M must have definitive answer before the p(n)-th step. If not, then we are sure that x is not an element of L.

The non-constructive part of the proof is when the proof uses polynomial bound p(n). The only thing that is given is the fact that L \in {\bf P}, and the question is how can we find a polynomial bound for L? Is there a constructive method to find such polynomial p?

From Las Vegas to Monte Carlo with Markov’s Inequality

One of the basic results in probability theory tells us that it is unlikely a random event deviates from its expected value with high probability.
Theorem 1. (Markov’s Inequality)
For any non-negative real valued random variable X, we have
{\text Pr}[X \ge \alpha] \le \frac{\mathbb{E}[X]}{\alpha}.

Note that
\mathbb{E}[X] = \sum_{x \ge 0} x \cdotp p_X(x)
= \underbrace{\sum_{x<\alpha} x \cdotp p_X(x)}_{\ge 0} + \sum_{x \ge \alpha} x \cdotp p_X(x)
\ge \sum_{x \ge \alpha} \alpha \cdotp p_X(x)
\ge \alpha \cdotp \text{Pr}[X \ge \alpha],
as desired. \Box

There is an interesting application of this inequality in theoretical computer science. Knowing this probability bound, it allows us to control a probabilistic algorithm derived from another probabilistic algorithm.

There are at least two classes of probabilistic algorithms that are interesting when we look at in which aspect it is random:

  • a class of algorithms whose output is always correct, but its running time is random (can take very long time),
  • a class of algorithms whose running time is deterministic (for example, is a deterministic function in the length of input), but its answer is sometimes wrong.

The first class is usually called Las Vegas algorithm and the second class is usually called Monte Carlo algorithm. How are these two algorithms related?

It appears that if we can solve a problem using Las Vegas algorithm, we can also solve it using a Monte Carlo algorithm with reasonably small error probability. Let me argue why this is a useful fact. For many practical purposes, we want to have a decision right after certain amount of time; it is okay to make mistakes sometimes (as we may be able to handle it later).

To obtain a Monte Carlo algorithm, we can just simulate the Las Vegas algorithm with little modifications. Our modifications aim at fulfilling two requirements: it runs in a “fixed” time and it outputs an answer in a reasonably good probability. To fulfill the first requirement, we can just fix a threshold for the number of computational steps the Las Vegas algorithm takes, say t(x) steps for an input of size x. If after t(x) steps, our Las Vegas algorithm outputs an answer, we can just output the same answer in our Monte Carlo algorithm. This will always be a correct answer by the nature of Las Vegas algorithm. If not, we just output a made-up answer (depending on our need).

But, how should we choose t(x)? We have freedom here to choose the function t(x), but we may want to use this to fulfill the second requirement: to get a correct answer with good probability. Note that we can analyze our Las Vegas algorithm to obtain its expected running time on input x, say p(x). We know that our Monte Carlo algorithm will output a correct answer at least when the simulation finishes in t(x) steps. If X is the running time of the simulation of our Las Vegas algorithm, then the probability of having a correct answer is at least
\text{Pr}[X < t(x)] = 1- \text{Pr} [ X \ge t(x) ]
\ge 1 - \frac{ \mathbb{E}[X] }{t(x)}
= 1- \frac{p(x)}{3p(x)}
= \frac23,
which is good, if we pick t(x)=3p(x). Obviously, we can also pick larger t(x) to gain better probability. But, as long as we pick t(x)>2p(x), we can also amplify this probability by doing multiple simulations and process a final answer (in case of Boolean answer, for example, we do majority voting).

Note that we have described an abstraction of how to transform any Las Vegas algorithm to a Monte Carlo algorithm. This can be very useful if instead of getting an always-correct-answer, we know when we will get an answer and maybe do a post-processing to the answer afterwards.

Now, our curious mind would ask: Can we obtain a Las Vegas algorithm from a Monte Carlo algorithm? If yes, how? If not, why is it not allowed by nature? Are the collection of problems that can be solved using Las Vegas algorithms and the collection of problems that can be solved using Monte Carlo algorithms the same? If we talk about polytime algorithm, a mathematical-minded reader may want to read more about complexity class {\bf ZPP}, {\bf BPP}, and possibly other probabilistic complexity classes.