patternMinor
A metaphor for recursive enumerability
Viewed 0 times
recursiveforenumerabilitymetaphor
Problem
In his commentary on a case involving pornography in 1964, U.S. Supreme Court Justice Potter Stewart sidestepped the question of defining what it meant for a work to be pornographic, but then said "I know it when I see it." It struck me that this was a pretty good description of recursive enumerability (recognizability): he was asserting that he was a recognizer for the set of all creative events, broadly construed, that were pornographic. By saying that he wouldn't, and perhaps couldn't, define pornography, he was saying that as far as he was concerned, pornography was not recursive, in that while he could answer "yes" to the question "is this work pornographic?" he couldn't correctly answer "no" in all cases, saying, in effect, that the set of pornographic events wasn't recursive (decidable). In short, he claimed, metaphorically, the set PORN was in $RE\setminus R$.
Pedagogically, this metaphor might work well as an aside when I introduce $RE$ and $R$ to my students, but I'm not entirely happy with it, since it seems feasible that another jurist might very well assert that s/he could indeed determine, for all possible creative events, $e$, whether $e$ was not pornographic. The question is, is there a "tighter" real-world metaphor, where we could agree that determining whether $e$ is a member of $P$ is obviously possible, but determining that $e\notin P$ for all $e$ is obviously impossible?
Pedagogically, this metaphor might work well as an aside when I introduce $RE$ and $R$ to my students, but I'm not entirely happy with it, since it seems feasible that another jurist might very well assert that s/he could indeed determine, for all possible creative events, $e$, whether $e$ was not pornographic. The question is, is there a "tighter" real-world metaphor, where we could agree that determining whether $e$ is a member of $P$ is obviously possible, but determining that $e\notin P$ for all $e$ is obviously impossible?
Solution
I was first taken by your metaphore, but I do not think it works.
Actually he is saying that he is himself a decision procedure, though
he cannot describe his own internal program. Hence Justice Stewart
decisions are recursive, not recursively enumerable, at least where
pornography is concerned. I would indeed expect anyone capable of such
an arrogant statement to be computationally limited.
Now for other examples taken from the real world, the first that comes
to mind is actually co-RE, though that amounts to the complement being
RE. It is the buggy program problem. If a program has a bug, it will
show some day, provided we use it long enough. But we cannot be sure
thre are no bugs, even when none has been found. Well, that was before
we could prove program correct (not that we are really there yet).
A close problem is falsifiability of scientific theories, as defined by
Karl Popper. The idea is that science is primarily co-RE:
A theory in the empirical sciences can never be proven, but it nust
be falsifiable, meaning that it can and should be scrutinised by
decisive experiments that could prove it wrong.
In other words, all we can know for certain, is that some empirical
science theories are false, because some consequences have been
experimentally proved false.
Whatever remain might be good theories, unless later proved false.
False theories form a RE set. Good theories are the co-RE complement.
But I am not sure this last example will make things clearer for your
students.
And the relations between scientific theories, or their correctness
status are a bit more subtle than that.
P.S. I think mortal people form an RE set.
Actually he is saying that he is himself a decision procedure, though
he cannot describe his own internal program. Hence Justice Stewart
decisions are recursive, not recursively enumerable, at least where
pornography is concerned. I would indeed expect anyone capable of such
an arrogant statement to be computationally limited.
Now for other examples taken from the real world, the first that comes
to mind is actually co-RE, though that amounts to the complement being
RE. It is the buggy program problem. If a program has a bug, it will
show some day, provided we use it long enough. But we cannot be sure
thre are no bugs, even when none has been found. Well, that was before
we could prove program correct (not that we are really there yet).
A close problem is falsifiability of scientific theories, as defined by
Karl Popper. The idea is that science is primarily co-RE:
A theory in the empirical sciences can never be proven, but it nust
be falsifiable, meaning that it can and should be scrutinised by
decisive experiments that could prove it wrong.
In other words, all we can know for certain, is that some empirical
science theories are false, because some consequences have been
experimentally proved false.
Whatever remain might be good theories, unless later proved false.
False theories form a RE set. Good theories are the co-RE complement.
But I am not sure this last example will make things clearer for your
students.
And the relations between scientific theories, or their correctness
status are a bit more subtle than that.
P.S. I think mortal people form an RE set.
Context
StackExchange Computer Science Q#43941, answer score: 5
Revisions (0)
No revisions yet.