Indirect self-reference: Difference between revisions

Content deleted Content added

Inline

Latest revision as of 15:31, 26 July 2024

Indirect self-reference describes an object referring to itself indirectly.

For example, define the function f such that f(x) = x(x). Any function passed as an argument to f is invoked with itself as an argument, and thus in any use of that argument is indirectly referring to itself.

This example is similar to the Scheme expression "((lambda(x)(x x)) (lambda(x)(x x)))", which is expanded to itself by beta reduction, and so its evaluation loops indefinitely despite the lack of explicit looping constructs. An equivalent example can be formulated in lambda calculus.

Indirect self-reference is special in that its self-referential quality is not explicit, as it is in the sentence "this sentence is false." The phrase "this sentence" refers directly to the sentence as a whole. An indirectly self-referential sentence would replace the phrase "this sentence" with an expression that effectively still referred to the sentence, but did not use the pronoun "this."

An example will help to explain this. Suppose we define the quine of a phrase to be the quotation of the phrase followed by the phrase itself. So, the quine of:

is a sentence fragment

would be:

"is a sentence fragment" is a sentence fragment

which, incidentally, is a true statement.

Now consider the sentence:

"when quined, makes quite a statement" when quined, makes quite a statement

The quotation here, plus the phrase "when quined," indirectly refers to the entire sentence. The importance of this fact is that the remainder of the sentence, the phrase "makes quite a statement," can now make a statement about the sentence as a whole. If we had used a pronoun for this, we could have written something like "this sentence makes quite a statement."

It seems silly to go through this trouble when pronouns will suffice (and when they make more sense to the casual reader), but in systems of mathematical logic, there is generally no analog of the pronoun. It is somewhat surprising, in fact, that self-reference can be achieved at all in these systems.

Upon closer inspection, it can be seen that in fact, the Scheme example above uses a quine, and f is actually the quine function itself.

Indirect self-reference was studied in great depth by W. V. Quine (after whom the operation above is named), and occupies a central place in the proof of Gödel's incompleteness theorem. Among the paradoxical statements developed by Quine is the following:

"yields a false statement when preceded by its quotation" yields a false statement when preceded by its quotation

References

@@ Line 1: / Line 1: @@
+{{Unreferenced|date=December 2009}}
 '''Indirect self-reference''' describes an object [[self-reference|referring to itself]] ''indirectly''.
-For example, define the function f such that f(x) = "x(x)". Then, the object f(f) = "f(f)". This object could be seen as indirectly referring to itself.
+For example, define the function f such that f(x) = x(x). Any function passed as an argument to f is invoked with itself as an argument, and thus in any use of that argument is indirectly referring to itself.
-This example is similar to the [[Scheme_programming_language|Scheme]] expression "((lambda(x)(x x)) (lambda(x)(x x))" which evaluates to itself, and therefore implements an infinite loop without using any looping constructs.
+This example is similar to the [[Scheme (programming language)|Scheme]] expression "((lambda(x)(x x)) (lambda(x)(x x)))", which is expanded to itself by beta reduction, and so its evaluation loops indefinitely despite the lack of explicit looping constructs. An equivalent example can be formulated in [[lambda calculus]].
 Indirect self-reference is special in that its self-referential quality is not explicit, as it is in the sentence "this sentence is false." The phrase "this sentence" refers directly to the sentence as a whole. An indirectly self-referential sentence would replace the phrase "this sentence" with an expression that effectively still referred to the sentence, but did not use the pronoun "this."
-An example will help to explain this. Suppose we define the [[quine]] of a phrase to be the quotation of the phrase followed by the phrase itself. So, the quine of:
+An example will help to explain this. Suppose we define the [[quine (computing)|quine]] of a phrase to be the quotation of the phrase followed by the phrase itself. So, the quine of:
  is a sentence fragment
 would be:
@@ Line 16: / Line 17: @@
  "when quined, makes quite a statement" when quined, makes quite a statement
-The quotation here, plus the phrase "when quined," indirectly refers to the entire sentence! The importance of this fact is that the remainder of the sentence, the phrase "makes quite a statement," can now make a statement about the sentence as a whole. If we had used a pronoun for this, we could have written something like "this sentence makes quite a statement."
+The quotation here, plus the phrase "when quined," indirectly refers to the entire sentence. The importance of this fact is that the remainder of the sentence, the phrase "makes quite a statement," can now make a statement about the sentence as a whole. If we had used a pronoun for this, we could have written something like "this sentence makes quite a statement."
-It seems silly to go through this trouble when pronouns will suffice (and when they make more sense to the casual reader), but in systems of [[mathematical_logic]], there is generally no analog of the pronoun. It is somewhat surprising, in fact, that self-reference can be acheived at all in these systems.
+It seems silly to go through this trouble when pronouns will suffice (and when they make more sense to the casual reader), but in systems of [[mathematical logic]], there is generally no analog of the pronoun. It is somewhat surprising, in fact, that self-reference can be achieved at all in these systems.
-Upon closer inspection, it can be seen that in fact, the [[Scheme_programming_language|Scheme]] example above uses a [[quine]], and f(x) is actually the [[quine]] function itself!
+Upon closer inspection, it can be seen that in fact, the [[Scheme (programming language)|Scheme]] example above uses a [[quine (computing)|quine]], and f is actually the quine function itself.
-Indirect self-reference was studied in great depth by [[W. V. Quine]] (after whom the operation above is named), and occupies a central place in the proof of [[Gödel's incompleteness theorem]].
+Indirect self-reference was studied in great depth by [[Willard Van Orman Quine|W. V. Quine]] (after whom the operation above is named), and occupies a central place in the proof of [[Gödel's incompleteness theorem]].  Among the paradoxical statements developed by Quine is the following:
+ "yields a false statement when preceded by its quotation" yields a false statement when preceded by its quotation
-See also:
+==See also==
+* [[Actor model]]
+* [[Diagonal lemma]]
 * [[Fixed point (mathematics)|Fixed point]]
-* [[Quine]]
+* [[Fixed point combinator]]
+* [[Gödel, Escher, Bach]]
 * [[Indirection]]
 * [[Self-interpreter]]
-* ISBN 0465026567
+==References==
+{{reflist}}
+{{DEFAULTSORT:Indirect Self-Reference}}
+[[Category:Self-reference]]
+[[Category:Theoretical computer science]]