WT:WPM HALTING PROOF BY MUSATOV ON WIKIPEDIA
}niaM olleH dlroW ediW beW gro.imaem.www\\:ptth:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
From Wikipedia, the free encyclopedia
Jump to: navigation, search
Shortcut:
WT:WPM
editArchives
List of all archives
2008: Jan · Feb · Mar · Apr · May · Jun · Jul · Aug · Sep · Oct · Nov
· Dec
2009: Jan · Feb · Mar · Apr · May · Jun · Jul · Aug · Sep · Oct · Nov
· Dec
Contents [hide]
1 Synergetics coordinates
2 Halting problem and Likebox
2.1 Also Gödel's incompleteness theorems
2.2 Link to ANI thread
2.3 An article on computing theory based proof?
3 "Infoboxes" on number articles
3.1 Objection to removal of infoboxes
3.2 Irrational numbers infobox
3.3 Infobox with various expansions
4 I was referred to post here
4.1 Tfd
4.2 Suggestion
4.3 Mea culpa, mea culpa, mea maxima culpa
4.4 And now a question for Finell (or others)
5 Differential algebraic equation
6 Markov chain
7 Uniform Polychora Project RfD
8 Errors in polyomino diagrams
9 Elementary proof on AfD
10 Flexagons
11 Notability of certain positional numeral systems
12 RFC to rename e from constant to number
13 Pentagram
14 Help with citations
[edit] Synergetics coordinates
Can someone take a look at Synergetics coordinates? I'm not much sure
what they are, but the page gets changed from time to time. They seem
to be related or unrelated to Synergetics (Fuller), and/or a Clifford
J. Nelson, and the latest edits are by a User:Cjnelson9. Shreevatsa
(talk) 04:20, 9 October 2009 (UTC)
It all sounds a bit like Sacred geometry to me, I'm not sure an
approach as mathematics would satisfy adherents who came along to read
about it. Dmcq (talk) 15:26, 9 October 2009 (UTC)
Is there any reason not to prod the article? This article seems to
flout just about every policy: WP:OR, WP:COI, WP:FORK, and so forth.
74.98.46.147 (talk) 22:28, 10 October 2009 (UTC)
Just now saw this discussion. The article was "prodded" on Oct 10, and
I "de-prodded" on Oct 15, since I think that the article ought to go
through AFD before being deleted. Paul August ☎ 20:15, 20 October 2009
(UTC)
[edit] Halting problem and Likebox
In my opinion, he's at it again. I can't find any restrictions he may
be under, but he's reformulating the halting problem to remove the
input, claiming it's the "modern" approach; and then adding a "modern
proof", replacing the diagonalization by quining. I'm at 3RR, but I
believe he is, also. Any input as to whether any of his assertions are
correct (whether or not "input" is "modern", the proof uses inputs)
would be appreciated. — Arthur Rubin (talk) 01:17, 15 October 2009
(UTC)
First, you aren't at 3RR, and neither am I. You are at "1R", and I am
at "2R". If you revert some of the material, I'll discuss.
Second, yes, I'm "at it again", because I was annoyed the first time
that people would not accept discussions which sound a little
different than textbooks. There are some proposed guidelines which I
think help: WP:ESCA, and perhaps with these guidelines, consensus can
be made to swing the other way.
I have no complaints with your behavior, and I understand and
sympathize with your position. I just disagree.Likebox (talk) 01:21,
15 October 2009 (UTC)
While I agree with both your points, the canonical description of the
Halting problem is with input. See the most modern book in Complexity
theory (Arora and Barak's 2009 text); even that treats the version
with input. While I like the quining and no-input version, that
shouldn't be the main version in the article. I believe a separate
section should highlight the formulation without inputs with the
quining proof. --Robin (talk) 01:44, 15 October 2009 (UTC)
But the same book surely states the theorem with no input too
somewhere. That's also a standard result. For example, Wolfram
mathworld states it without input.
Also from googling:
As an example of his thought let's look at a proof that there is no
way of telling in general once a computer has embarked on a
calculation whether that calculation will terminate in an answer. This
problem is known as the "Halting Problem for Turing machines" and was
first proved in the 1937 paper[2] in which he introduced his machines.
Again, no input. I have found cases where people state it with input,
and others where it is stated without. Since both are true, both are
almost identical, and the input is only there to simplify the proof a
tiny bit, I think it is misleading to make the input so prominent in
the lead.Likebox (talk) 01:57, 15 October 2009 (UTC)
As I said, I appreciate your point, and I do like the no-input
version, but the article's lead section should have the canonical
version which everyone is used to reading in their first year CS
course. Moreover, I think the diagonalization proof is easier for a
new reader. Once the reader has grasped this, the reader can move on
to the no-input version and quining proof. --Robin (talk) 02:04, 15
October 2009 (UTC)
Mm. I am far from knowledgeable about computation, but I just took a
look at Sipser (which I understand to be something of a standard
introductory text in the subject), and he uses finite input strings in
his description. I think, if people knowledgeable on the subject are
not in agreement to the contrary, we should probably stick to the
standard pedagogical approach. It's fairly common for there to be
sections towards the end describing generalizations and extensions of
the theory, however, so that might be a good place for Likebox to put
his stuff? RayTalk 01:38, 15 October 2009 (UTC)
The issue is entirely pedagogical. I agree that textbooks do not often
mention quines in this context, but I feel that this is a pedagogical
mistake. People knowledgable in the subject don't think about this,
because it is too elementary to waste time thinking about. It is in
these situations that bad pedagogy can flourish.
But we don't have to be stuck with bad pedagogy. If there is a nice
text which explains sourced material well, but doesn't sound exactly
like a textbook, that's OK according to WP:ESCA, so long as it is
accurate, clear, and explains intermediate steps in well referenced
results.
In this case, the theorem is this: You can't write a program HALT
which takes P as input and decides if P halts or not.
One way to state the proof is: Write SPITE to print its own code into
R, calculate HALT with input R, and if the answer is "R halts" go into
an infinite loop, and if the answer is "R doesn't halt" to halt.
This proof is trivial, and the only question is whether a program can
be made to write its own code. This is slightly nontrivial, but it is
an exercise for computer science freshman.
The other way to prove this is to say "It is undecidable whether
program P with input I halts for arbitary P and I". Then you prove it
this way. Suppose HALT(P,I) tells you whether P and I halts. Then
write SPITE to take input I, and evaluate HALT(I,I), and if the answer
is "I halts on input I" SPITE goes into an infinite loop. If the
answer is "I does not halt on input I" then SPITE halts.
Then you ask if SPITE is given as input the code for SPITE, what does
it do? You see, it's exactly the same proof, except that the code for
SPITE is given to SPITE as input, instead of being generated by SPITE
at step 1.
I think that the proof where SPITE prints its own code is clearer. To
prove that a program can always print its own code is very simple,
using the diagonalization argument.Likebox (talk) 01:52, 15 October
2009 (UTC)
I disagree with Likebox's opinion that Wikipedia should promote
pedagogical innovations not present in standard textbooks like stating
the Halting Problem the way he likes it. Pcap ping 07:41, 17 October
2009 (UTC)
[edit] Also Gödel's incompleteness theorems
The same issue at Gödel's incompleteness theorems, where Likebox has
previously added "modern" proof that was removed. It helps to have
more eyes on these pages. — Carl (CBM · talk) 02:05, 15 October 2009
(UTC)
This is particularly problematic because Likebox tends to revert the
removal of his proofs. — Carl (CBM · talk) 02:10, 15 October 2009
(UTC)
I don't like it when people delete 8K of material written over several
hours without discussion. It's impolite to the effort I put into the
new text. I know you have issues with this stuff, but mull it over.
These proofs are sorely needed. I have had discussions about this with
five or six mathematics students over the past week, and their
encouragement is the only reason I came back to these pages. The
current proofs of Godel's theorem is illegible, and it is beyond the
grasp of most undergraduates. That needs to change, and WP:ESCA is a
good way to allow it to change.Likebox (talk) 02:13, 15 October 2009
(UTC)
The issue was discussed, in depth, more than once. For example, see
this discussion in 2007. — Carl (CBM · talk) 02:15, 15 October 2009
(UTC)
Although I agree that the main proof should be the one in the article,
I do like Likebox's computer-sciencey proof. Maybe there's some way to
have Likebox's proof too, without having it as the main proof in the
article? Or perhaps put it in the Proof Sketch article, as an
alternative proof sketch? --Robin (talk) 02:18, 15 October 2009 (UTC)
Even if we did want to include Likebox's proof in the article, we
would need to rewrite it significantly to fix the terminology to match
the literature, and to make the tone encyclopedic rather than
pedagogical. Based on past experience, I do not believe Likebox
accepts such rewrites. — Carl (CBM · talk) 02:26, 15 October 2009
(UTC)
Right, I agree with you. I have no prior experience with Likebox, so I
can't say anything about the problem you mentioned. I have seen a
CSish proof of Godel's incompleteness in Scott Aaronson's lecture
notes. Perhaps this will help? --Robin (talk) 02:41, 15 October 2009
(UTC)
The proof that Likebox is inserting is actually the same as the proof
already there, just rephrased to use words like "program" and
"quine" (the latter incorrectly). If we were to rephrase Likebox's
proof into standard terminology it would simply be the usual proof via
the diagonal lemma. This is the proof presented by mainstream
mathematical logic texts. This has been explained to Likebox before. —
Carl (CBM · talk) 02:49, 15 October 2009 (UTC)
I see what you're saying. This explains the fact that there aren't a
multitude of texts out there with Likebox's proof: because both proofs
are essentially equivalent, and after formalizing Likebox's proof, you
end up with something similar to the original proof. --Robin (talk)
03:41, 15 October 2009 (UTC)
Note: I have posted about this to [1]. — Carl (CBM · talk) 02:26, 15
October 2009 (UTC)
There is no OR in this proof, it is equivalent to standard proofs, as
CBM has said. The issues are with what type of material can be
included here.
To Robin: the reason the proof is not presented the way I present it
is not because it is harder to formalize. The proof I give is at least
as simple to formalize as standard proofs. It's a little easier, in
fact, because the formal structure of modern computers is already well
understood.
But even though the logic is equivalent, style is very important. The
style of proof that I gave, now presented on Godel's incompleteness
theorems talk page, is vastly easier for undergraduates and non-
specialists to understand. It is also easier for most specialists to
understand, especially regarding Rosser's proof (which is a notorious
sticking point for students). In my experience, a presentation of the
proof in this style takes about 10-20 minutes to fully internalize and
understand, while the standard presentations take days or weeks of
intensive study to fully understand. Needless to say, learning the
easy proof allows students to then understand the standard proof much
more quickly. The proof I gave can be understood by any layperson who
is somewhat familiar with mathematics.
If you support the material, realize that politics is now slightly
against these types of proofs. There are two editors, CBM and Arthur
Rubin, who oppose this material. They oppose it mostly by inertia,
this is not the first time I have tried to incorporate the material.
It requires more editors with a strong opinion for inclusion to get
this material into the article.Likebox (talk) 20:40, 15 October 2009
(UTC)
I see no compelling reason not to use the standard proof (not the
Likebox version) Verbal chat 16:28, 16 October 2009 (UTC)
After a long discussion with Likebox and CBM, I also feel that we
should use the standard proof (the one that appears in text books). --
Robin (talk) 17:06, 16 October 2009 (UTC)
Silly people--- have you not read the proofs? What is this? The quine
presentation of Godel's theorem is 10 times better, and it does not
replace the other proof, it augments it. I don't understand why
opinion here swings one way, and opinion of people I talk to in person
swings the other way. It's definitely odd.Likebox (talk) 03:35, 19
October 2009 (UTC)
The difference is probably that here, you are running into people that
are more than capable of being your intellectual equal, versus your
students, no matter how bright, are going to be very easy to convince
of anything you like. Indeed, I just convinced a class for a few
minutes at least that there is actually an inconsistency in Peano
arithmetic but that there is an adult conspiracy to keep this hidden
from children until the contradiction becomes too obvious after you
learn about complex numbers (no, I'm not joking). --C S (talk) 11:31,
21 October 2009 (UTC)
I realize the point of your post was to say why people here might
respond differently than students, and I agree with your assessment
about that, but I am uncomfortable with threads discussing who is the
intellectual equal of whom. I think that the main reason for us to
focus on what the sources say, even when we have articles written by
experts in the field, is so that we can avoid having to make these
sorts of comparisons. Of course if you ask three experts to write an
article from first principles, you will get disagreements and
arguments about the best way to present the material. This is why
there are so many books on elementary group theory, elementary real
analysis, etc., and it is why the Bourbaki project is so remarkable.
But if you ask three experts to write an article that simply condenses
and summarizes the existing literature, without adding any personal
interpretation of how the literature "should be", they can do this
with much less difficulty. — Carl (CBM · talk) 12:37, 21 October 2009
(UTC)
[edit] Link to ANI thread
Because Likebox has added the proofs again after the discussion here
and at WP:NORB was clearly against them, I have raised the matter
here. Comments from all users are welcome there, despite the name of
the page. — Carl (CBM · talk) 00:48, 19 October 2009 (UTC)
Here's the correct link: WP:ANI#User:Likebox and tendentious re-
insertion of original research. — Emil J. 12:12, 19 October 2009 (UTC)
[edit] An article on computing theory based proof?
I am not keen on having the computer type proof in the Godel article,
but I think the approach is I believe notable because a number of
people have used it and it does convey the underlying ideas nicely.
Can't say either I like the 'it is obvious that' in the text Likebox
put in but there may be a way to show the status of things like that.
-- Perhaps it should be called an advanced proof in the tradition of
'Advanced algebra' and 'Elements of number theory'. ;-) Dmcq (talk)
13:53, 21 October 2009 (UTC)
Oh dear. I've had a good read of that ANI and it all reminds me of
WP:The Truth. Dmcq (talk) 14:27, 21 October 2009 (UTC)
The main difficulty with Likebox's proof is that there really are not
sources for it as it is literally written, but once one changes back
to standard terminology, the proof is already described in Gödel's
incompleteness theorems in the section "Relationship with
computability".
There are two "regular" ways of presenting a proof of the
incompleteness theorem via computability, which are actually very
similar to each other:
1.Via the fact that any consistent, computable extension of Robinson
arithmetic is incomplete; this is the method used by Shoenfield in
Mathematical logic. A weaker version is given by Enderton in A
mathematical introduction to logic. This method is characterized by
its use of the fact that a consistent, complete, computably
axiomatized theory is decidable. It is also characterized by the fact
that it does not produce any concrete Gödel sentence.
2.Via Kleene's T predicate, which is used to replace the provability
predicate in what is essentially a rewrite of Gödel's syntactic proof.
This gives a refinement of the first method, in which the Gödel
sentence can actually be written down. Kleene uses this method in
Introduction to metamathematics.
Likebox's text is, in the end, a rewording of the second method into
idiosyncratic terminology. It would be possible to reword the proofs
to make the terminology standard, but Likebox has argued against that
because he claims that the standard terminology is bad and should not
be used. — Carl (CBM · talk) 14:53, 21 October 2009 (UTC)
[edit] "Infoboxes" on number articles
List of numbers – Irrational numbers
ζ(3) – √2 – √3 – √5 – φ – α – e – π – δ
List of numbers – Irrational numbers
γ - ζ(3) – √2 – √3 – √5 – φ – α – e – π – δ
Number System Evaluation of π
Binary 11.00100100001111110110…
Decimal 3.14159265358979323846264338327950288…
Hexadecimal 3.243F6A8885A308D31319…
Rational approximations 22⁄7, 223⁄71, 355⁄113, ...
(listed in order of increasing accuracy)
Continued fraction [3; 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, 2, 1,
1, … ][1]
(This continued fraction is not periodic. Shown in linear notation)
Trigonometry π radians = 180 degrees
1.^ A001203: Continued fraction for Pi, On-Line Encyclopedia of
Integer Sequences
Earlier today I tried to remove the "infobox" (displayed right), from
e (mathematical constant), since it doesn't seem to me to add much of
use to the article (as well as the fact that the links listed seem a
bit arbitrary), I was reverted with the comment "the same template is
used in the aticle about pi and all of the other irrational numbers of
interest". And in fact the article for each of the constants listed in
that infobox contains the infobox, and some have sprouted more
expansive infoboxes (e.g. see the infobox for Pi displayed right).
What do others think about these? Paul August ☎ 18:13, 17 October 2009
(UTC)
I believe the pi infobox is pretty frivolous for a lot of reasons.
First, putting links to list of numbers and irrational number is not
informative. Second, linking to other "irrational" numbers is
unnecessary. Third, pi's hexadecimal and binary expansions add
absolutely no insights into the nature of this number. Neither does
the continued fraction expansion (that would make sense for numbers
where the continued fraction expansion has a pattern or defines the
number). Ditto about the rational approximations.
All in all, while some people may think infoboxes are pretty and
summarize some properties, this particular one adds no value I can
see. I'd say we should cut it out. Oleg Alexandrov (talk) 22:20, 17
October 2009 (UTC)
I agree. The irrational numbers infobox is silly, and the pi infobox
is obnoxious. Both should be removed. Ozob (talk) 00:55, 18 October
2009 (UTC)
It seems to me that these particular infoboxes, even more than
infoboxes in general, are just infotainment. I don't mind them very
strongly, but I am also inclined towards removing them. Hans Adler
01:09, 18 October 2009 (UTC)
What is "rational approximations" is supposed to mean? Isn't 3.14 a
rational approximation? I was thinking it would be the best
approximations for a given bound on the denominator, but then the
entire list would be 3/1, 13/4, 16/5, 19/6, 22/7, 179/57, 201/64,
223/71, 245/78, 267/85, 289/92, 311/99, 333/106, 355/113, ... which is
a lot more than what's listed. It's kind of a general problem with
infoboxes that no one seems to check that they're accurate.--RDBury
(talk) 05:12, 18 October 2009 (UTC)
What's typically listed as rational approximations are the convergents
(aka approximants) of the continued fraction representation, but maybe
we should also include all those you mentioned, which can also be
obtained from the CF as described at
Continued_fraction#Best_rational_approximations. Dicklyon (talk)
19:29, 23 October 2009 (UTC)
While it is clear that the infobox adds no insight about the nature of
π and is of no value to mathematicians (and also that its location in
the article is distracting and "obnoxious"), perhaps we should check
if the binary and hexadecimal forms are of any use to, say,
programmers (why were they put there in the first place?). About
infoboxes in general, there is nothing wrong with infotainment per se;
articles don't have to cater only to readers who actually read the
whole thing (who are a tiny minority, of course). :-) Shreevatsa
(talk) 06:01, 18 October 2009 (UTC)
I was thinking about that but I'm pretty sure that modern assemblers
are smart enough to convert decimal into binary for programming
purposes.--RDBury (talk) 06:46, 18 October 2009 (UTC)
Thanks to everyone for sharing your views. Based upon the above
discussion, I intend to remove the infoboxes, and will leave a note on
the involved articles' talk pages, as well as on the talk page of the
reverting editor (Robo37), pointing to this discussion and asking
anyone who disagree to please join this discussion.
Not that that it matters particularly, but I've discovered that the
infoboxes were added, for the most part it seems, by two apparent
sockpuppets (Anton Mravcek (talk · contribs) and PrimeFan (talk ·
contribs)) of Dmetric (talk · contribs), all of whom (as well as many
more see Category:Wikipedia sockpuppets of Dmetric) have been blocked.
Paul August ☎ 12:25, 18 October 2009 (UTC)
I think a lot of casual readers might like that sort of infotainment.
Not everyone wants the hard facts and theorems. Some people just want
to see other wacky numbers like Pi (and would be led to phi, sqrt(2),
e, etc.). --Robin (talk) 16:18, 18 October 2009 (UTC)
There are better ways to infotain yourself than to watch the parade of
all imaginable pi representations which have nothing to do with pi's
purpose. Oleg Alexandrov (talk) 16:26, 18 October 2009 (UTC)
I was defending the "ζ(3) – √2 – √3 – √5 – φ – α – e – π – δ" part,
which might be fun for casual readers. The hexadecimal representation
of pi is probably completely useless to everyone. --Robin (talk)
17:22, 18 October 2009 (UTC)
That is really a completely absurd list of "irrational numbers".
There's no link between them and how are α and δ even on such a list.
I find ζ(2) much more interesting than ζ(3), for example. I find the
argument against that infobox is more that it's an absurd list. A more
suitable list would be like a list of numbers that have been studied
for forever (π, e, φ, √2, -1, i). RobHar (talk) 18:39, 18 October 2009
(UTC)
[edit] Objection to removal of infoboxes
I disagree strongly with the removal of the infoboxes, and especially
with the way it was done. First, one editor removed the infobox from e
(mathematical constant) with no talk page discussion and no pretense
of consensus, essentially because he doesn't like it. Unsurprisingly,
this was quickly reverted. Instead of discussing the removal and
revert on the article's talk page (see WP:BRD) with the editors who
have been maintaining the article and who evidently approve of the
infobox, the editor comes here. The editor does not even post notice
of this "discussion" on the talk page of that article or on the talk
pages of his other target articles. After 20 hours, during about 8 of
which most of us were asleep, still with no notice to the editors of
any of the articles, the discussion is closed. The editor who
initiated the discussion here then removes infoboxes from 10 articles,
and then posts notices on the articles' talk pages that invites anyone
who objects to join this discussion that has already reached its
conclusion.
I object.
Two types of infoboxes were removed:
The short, one-line type guides readers to articles on other notable
irrational numbers. While not enlightening to the mathematicians here,
this navigation box is helpful to high school and college students and
other general readers, who come to Wikipedia to learn about things
that they do not already know. These are the people for whom we are
building this free encyclopedia.
The longer type is hand-crafted for the particular article. It
consolidates useful information about the particular irrational number
in one place at the beginning article for easy reference. That is what
infoboxes are supposed to do.
I am restoring the infoboxes. Please do not remove any of them without
first reaching consensus to do so on the talk page of the particular
article. Thank you. Finell (Talk) 18:01, 18 October 2009 (UTC)
Do you intend to address any of the arguments above that the so-called
"useful information" is in fact largely useless? Algebraist 18:04, 18
October 2009 (UTC)
I support the restoration of the infoboxes, primarily because they
were removed with insufficient consensus or even notice on the
relevant articles. But in answer to some of the arguments above, I'd
say that the continued fraction expansion of pi is of fundamental
importance, as with other irrationals, in understanding the nature of
its rational approximations. And the binary and hexadecimal fractions
are the same kind of trivia as the decimal expansion, useless info
that nobody seems to have trouble with, but arguably more useful for
someone who wants to make an accurate approximate representation in a
computer – not a great reason, but what the heck, it's also
infotainment, as I made fun of at my favorite: Square root of 4.
Dicklyon (talk) 18:39, 18 October 2009 (UTC)
The continued fraction expansion of pi has no more value than its
rational approximation or than the hexadecimal representation. It is
just a sequence of numbers with no pattern and no insights. Granted,
this expansion is not useless, but it does not belong to the
"defining" or "illuminating" features which an infobox is supposed to
highlight. I would support the inclusion of the continued fraction
only at the golden ratio article. Oleg Alexandrov (talk) 18:47, 18
October 2009 (UTC)
I'm very surprised to hear you say that, given how often the continued
fraction of pi is explicitly displayed and discussed in relation to
some very special approximations to pi, for example in these many
books. Dicklyon (talk) 19:28, 18 October 2009 (UTC)
(ec fix)May I suggest splitting this up into two discussions: One
concerning the infobox about π to be held at
Talk:Pi#Removal_of_infobox, and the other about the infobox which I
will call "Irrational numbers infobox", to be held on this page. My
suggestion for holding the latter on this page is that the infobox
appears on several pages and I believe the issue at hand is not its
inclusion but rather its content (and if the infobox was a template
(as they usually are), the discussion would take place on the
template's talk page). In both cases, I suggest reinserting the
infoboxes into the articles to be in line with the BOLD, revert,
discuss cycle. I will start a new subsection below regarding the
"irrational numbers infobox". RobHar (talk) 18:57, 18 October 2009
(UTC)
Also: it appears the latter infobox sometimes also contains expansion
in various bases and continued fraction expansions, I'd suggest
discussing this in another subsection I will start below. RobHar
(talk) 19:11, 18 October 2009 (UTC)
Sounds like a good idea to discuss this centrally; but you need to
post a notification on the talk pages of each of the affected
articles, or you'll run into the same problem again. Dicklyon (talk)
19:28, 18 October 2009 (UTC)
Yes, I wanted to see if anybody agreed before doing that. I'll do it
now. RobHar (talk) 19:31, 18 October 2009 (UTC)
For a discussion about the infoboxes in question please see the two
following subsection and, for the infobox on pi, see
Talk:Pi#Removal_of_infobox. The discussion in this section is about
procedure (and in some sense the "past"). Finell has stated (in my
opinion correctly) that consensus for the removal should be obtained
before re-removing. The discussion above on this page was not
announced on the relevant article talk pages and those articles'
editors could not be aware of it. The infoboxes should be reinserted
pending us reaching a possibly new consensus in which the respective
articles' editors have been given the time to weight in. This is the
way of wiki (WP:BRD). If you have an objection to this, this section
is where you can voice that. Other discussion should go on in the
relevant other section. Ok, let's do this. Cheers. RobHar (talk)
21:10, 18 October 2009 (UTC)
The infoboxes are relevant and should remain. Drakcap (talk) 02:29, 19
October 2009 (UTC)
[edit] Irrational numbers infobox
It has been suggested above to remove the following infobox from all
articles it is on:
List of numbers – Irrational numbers
ζ(3) – √2 – √3 – √5 – φ – α – e – π – δ
To do this in a centralized location, I propose discussing this
infobox here.
My personal feelings are that the general idea of the infobox may be
appropriate, but the current list of numbers is absurd. α and δ are
nowhere near as notable as the other numbers, for example. Overall,
the list seems arbitrary. I think a list that could work would be (π,
e, φ, √2, -1, i) or (π, e, φ, √2), being lists of classically
important numbers. RobHar (talk) 19:03, 18 October 2009 (UTC)
It appears some of the articles also include the Euler–Mascheroni
constant. I feel that's not on the level of notability of (π, e, φ,
√2, -1, i) either. RobHar (talk) 19:13, 18 October 2009 (UTC)
(after edit conflict)
Some versions of this navigation box also include the Euler–Mascheroni
constant. Rational persons could disagree over a notability threshold,
and Wikipedians could argue about it for days, maybe weeks. The
purpose of the navigation box is to invite interested readers to
explore other irrational numbers. Being inclusive, within reason,
furthers this purpose. Please just leave it as is. It has not been a
problem for the long time during which these boxes have been in the
articles without complaint. Finell (Talk) 19:27, 18 October 2009 (UTC)
Sorry, but that's just not a practical way to approach this (though
you seem to be stating it is). It means the only current criterion for
being on the list is "Do I like this number?". This necessarily leads
to the problem that you complained of above regarding WP:IDL. I think ζ
(2) is much more interesting than ζ(3), γ, α, and δ. Can I add it?
RobHar (talk) 19:42, 18 October 2009 (UTC)
Wikipedia must not have an irrational numbers infobox. It will violate
policy. Creating such an infobox requires selecting a set of
irrational numbers to include: Some irrational numbers would be deemed
important enough to include, and others would not. Unless we can
attribute that selection to someone, the choice constitutes WP:OR. If
you can find someone who says, "The following irrational numbers are
the most important: ..." then we can create an infobox for "So-and-
so's list of important irrational numbers". But we cannot create that
list ourselves. Ozob (talk) 19:48, 18 October 2009 (UTC)
I recommend we base the selection on a good book, such as Mathematial
Constants, by Finch, chapter 1 "Well-Known Constants", and draw the
line at groups where the constants don't each have their own name and
symbol. The effect of this would be primarily to remove square roots
of 3 and 5 from the list, which would be OK by me. Dicklyon (talk)
20:05, 18 October 2009 (UTC)
It seems that this would also have the effect of adding Catalan's
constant, Madelung constant, Chaitin's constant, and removing the
Feigenbaum constants. Right? RobHar (talk) 20:20, 18 October 2009
(UTC)
He does give the two distinct symbols for the two Feigenbaum
constants, so let's keep those. And add ln2, also. And it's not clear
to me that Chaitin's constant is a constant, or what its value is, so
not sure on that one. Dicklyon (talk) 20:24, 18 October 2009 (UTC)
It just doesn't seem like an actual list of "well-known" constants. To
be honest, I don't really subscribe to the idea of using one source as
a definitive list of interesting numbers (or anything else for that
matter). Unless the infobox is called Steven Finch's list of well-
known mathematical constants. Such an infobox should only exist if
that list is notable, which in this case it is not. If Gauss, or
Hilbert, or someone of that stature compiled a list at some point,
that would be good. Otherwise, in my opinion, the best we could do
(that would result in including this infobox) would be determine some
sort of consensus on what the general literature considers well-known
mathematical constants, or what constants clearly appear everywhere.
RobHar (talk) 20:41, 18 October 2009 (UTC)
User:Robo37 has just taken on a more WP:POINTy approach, it appears,
which is to add every irrational he can find to the infobox. It seems
to me that we ought to have the discussion first. Dicklyon (talk)
20:29, 18 October 2009 (UTC)
Robo37's new version wraps, with just one character on a second line
(ugly), and is so wide that it degrades the layout of the lead. And he
in essence reverted Epstein's reverts of my reverts of the original
removal of the infoboxes? Why all this unilateral action with no
respect for existing consensus and no attempt to build a new
consensus? I have no prior experience with Project Math. Is this
standard operating procedure here? I hope not. Finell (Talk) 20:57, 18
October 2009 (UTC)
Sadly, minutiae like this tends to bring out the most petty and
juvenile among us. I agree with you entirely that adding a huge list
of irrationals is just disruptive. Ozob (talk) 21:45, 18 October 2009
(UTC)
He seems to have gone away for today. Anyone mind if I use the
rollback button on all those? Dicklyon (talk) 21:47, 18 October 2009
(UTC)
I think it would indeed be a good idea to rollback those edits to help
this discussion move forward. RobHar (talk) 22:24, 18 October 2009
(UTC)
The purpose of a list of numbers is not so much an infobox in a
specific number article but rather it is more a navigation template.
The purpose of a navigation template is to guide readers to other
articles on the same, or a related, subject, in this case to other
irrational number articles. The idea that you should only include well
known numbers - ie, ones that the reader has already heard of - is,
quite frankly, silly. The readers already knows where the pi article
is, they don't need a template to find it. The criterion for inclusion
should not be "notability", that is a criterion for deciding whether
the number should have an article at all, the criterion should be
"might a reader reading this article find x interesting also". This
could, of course, end up with a very long list, but there is no need
to point to every individual number article. On the other hand, the
template can and should point to lists of numbers or articles about
groups of numbers wherer the reader can find further links to
individual articles. Remember, readers are generally trying to find
something out from the encyclopedia, not just trying to confirm what
they already know. SpinningSpark 22:55, 18 October 2009 (UTC)
When I talk about notability, it's more a matter of relative
notability. I feel that the current list runs a wide gamut of
notability, skipping some important constants. I find it good to
direct the reader to other important numbers, but I also find it
misleading to link to some of the current numbers on the list. I do
like your idea of making an infobox that is a list of lists. The
current infobox does link to List of numbers. This list already
encompasses everything it seems. Are there other lists you're aware
of? RobHar (talk) 23:37, 18 October 2009 (UTC)
There is Transcendental number#Known transcendental numbers and open
problems but they are probably already all included in List of
numbers. Transcendental number and algebraic number should probably be
in the template somewhere and maybe transfinite number and complex
number as well. SpinningSpark 00:41, 19 October 2009 (UTC)
[edit] Infobox with various expansions
The articles on Apéry's constant, the square roots of 2, 3, and 5, the
Golden ratio, and the Euler–Mascheroni constant γ also include an
infobox containing expansions of these numbers in different bases and
continued fraction expansions. I propose discussing these infoboxes
here (for the discussion of the even bigger infobox about π I suggest
Talk:Pi#Removal_of_infobox). RobHar (talk) 19:20, 18 October 2009
(UTC)
Why start this controversy? How is this improving Wikipedia for its
readers? Are readers being misled or given erroneous information?
These infoboxes have been in these articles for a long time without
complaint or problem. Obviously, the editors who maintain the
individual articles approve of the infoboxes. However, if you feel the
need to discuss this anywhere, please do so on the individual talk
pages for the individual articles, so you engage the editors who
maintain the articles; the considerations may differ with each
article. And in the future, please don't presume to decide here, as a
project, to make mass changes to several articles without so much as a
word to the editors who wrote or maintain those articles. A little
respect for your co-editors would be in order. Thank you. Finell
(Talk) 19:42, 18 October 2009 (UTC)
But someone has raised a complaint, so I am proposing to deal with
this in a more sensible way than was done above. You may disagree with
how Paul August dealt with the infoboxes, but that is not what this
subsection of the discussion is for. To discuss that, you may start a
new subsection or bring it to an entirely different forum altogether.
As it stands, I have posted a notice on the talk page of every article
involved to discuss this here. I find this amply sufficient. I have
suggested that the infoboxes be reinserted into their articles (based
on prior consensus) until a new consensus is attained. I also find
this completely appropriate. Several editors have now raised
objections to these infoboxes, so the subject must be discussed.
That's just the way it is. Again, if you are unhappy with how that was
dealt with start a new section, I'd like for this section to be a new
discussion about the infobox in question. Cheers. RobHar (talk) 19:50,
18 October 2009 (UTC)
(interject after edit conflicts)
"You may disagree with how Paul August dealt with the infoboxes, but
that is not what this subsection of the discussion is for. To discuss
that, you may start a new subsection ..." That is what I did above,
and others forked it into these two subsections. Meanwhile, another
editor is now running around reverting my reverts of Paul's removal of
the infoboxes, taking the position that consensus is needed to revert
what Paul removed without consensus. Wikipedia doesn't need more
controversies like this. I don't see how it helps the encyclopedia,
and it certainly doesn't help the morale of the editors who worked on
the articles in question to see that the "project" has overridden
their consensus. In fact, I don't see anything on the consensus policy
page that permits a project to override the consensus of an article's,
or multiple articles', editors. Please restore the infoboxes that Paul
removed and leave them intact until there is real consensus of the
articles' editors to remove them, allowing several days for involved
editors (not just those who can monitor their watchlists 24/7) to
participate. Thank you. Finell (Talk) 20:34, 18 October 2009 (UTC)
Ah yes, I see what you are saying, sorry I confused myself. Indeed,
you started a section above about this, and it turned into a
discussion of whether or not the infoboxes should be included instead
of a discussion about the manner in which they were originally (and
subsequently) removed. I split off the "off-topic" discussion into
these two sections hoping that the discussion you started in
Wikipedia_talk:WikiProject_Mathematics#Objection_to_removal_of_infoboxes
could continue there, with discussion of the infoboxes themselves
moved to these two sections. Sorry for my confusion. RobHar (talk)
20:58, 18 October 2009 (UTC)
Myself, I believe that removing these infoboxes will make Wikipedia
easier to comprehend. As it stands, readers are not being given
incorrect facts; they are being given irrelevant facts. Undue weight
is being placed on things that are of no interest to anybody. The
binary and hexadecimal expansions of π are entirely useless. What
information do they give that any other expansion doesn't? If one of
these expressions were revealing in some way (in the same way that the
continued fraction expansions of φ and the square roots of 2, 3, and 5
are revealing), then there would be a good reason to keep it. If you
can demonstrate that these expansions are interesting to anyone
anywhere, then we'll have a reason to keep them. Until then, I will
cite WP:INDISCRIMINATE. Ozob (talk) 20:02, 18 October 2009 (UTC)
Personally, I kind of like infoboxes, as they tied interesting
collections of things together in interesting ways. But I'd prefer to
omit info that's not sourced – such as in the color infoboxes where
people are always adding their favorite or computed RGB, CMY, HSL,
HSV, LAB, etc. coordinates with no sourced basis at all. In the
irrational number infoboxes, I'd agree that we ought to omit binary
and hexadecimal expansions except where we can find a source to tie
them to. There are many sources about computing hexadecimal digits of
pi, but unless one of them actually lists the digits, let's don't. And
if we don't find sourced continued fractions, let's leave those out,
too (but for most of these I think we'll find them). Dicklyon (talk)
20:21, 18 October 2009 (UTC)
To me the problem is not so much sourcing any individual factoid in
these boxes — I'm not worried about correctness — as justifying their
inclusion. Why do we include ζ(3) but not ζ(2)? Because it's a trivial
variation of π? But then why do we include both √5 and φ when they're
trivial variations of each other. Why do we include base 2 and base 16
but not base 60 or base 1329? Etc. It's a WP:INDISCRIMINATE collection
of information, and it doesn't add anything useful to the text of the
article. —David Eppstein (talk) 21:03, 18 October 2009 (UTC)
I made a proposal in the subsection above about which numbers to
include, based on a source. As for which bases, didn't I just say to
include only stuff from sources? We might find a base-60 approximation
to pi that would be worth adding, but I wouldn't worry about base
1329. Dicklyon (talk) 21:32, 18 October 2009 (UTC)
In fact our sexagesimal article mentions two base-60 expansions of π.
That doesn't mean that it would be helpful information to modern
readers. —David Eppstein (talk) 21:57, 18 October 2009 (UTC)
[edit] I was referred to post here
Talk:Halting problem From Wikipedia, the free encyclopedia Jump to:
navigation, search [hide]WikiProject Mathematics (Rated Bplus-Class)
Mathematics portal
This article is within the scope of WikiProject Mathematics, a
collaborative effort to improve the coverage of Mathematics on
Wikipedia. If you would like to participate, please visit the project
page, where you can join the discussion and see a list of open tasks.
Mathematics rating: A-BB+ Class High Priority Field: Discrete
mathematics [show]Please update this rating as the article progresses,
or if the rating is inaccurate. Click to show/hide comments. Please
add to or update the comments to suggest improvements to the article.
Needs longer lead, more motivation and context. Geometry guy 21:41, 9
June 2007 (UTC)
Archives Talk:Halting Problem: 2001-2002
Archive 1: 2002–2005
Archive 2: 2006
Archive 3: 2007–2009
Contents [hide] 1 Has it been noted? 2 Problematic sentences 3 The
proof is invalid 4 Artificial Intelligence and the Halting Problem 5
Using randomness to solve halting problem 6 Modern Proof 7 Input
nonsense 8 Reverting the changes to the intro 9 See WT:MATH 10
Previous Likebox discussions 11 Mathematical problems as Halting
problem. 12 text th@ may likely be deleted by someone with an
unwholesome interest in p=/=np 13 ERROR 13.1 The requested URL could
not be retrieved 14 Complexity classes P and NP 14.1 Decision problems
14.2 NP+complete 14.3 Still harder problems 14.4 Why do computer
scientists think P ≠ NP? 14.5 Polynomial+time algorithms 14.6 Logical
characterizations 14.7 P and NP trivia 14.8 See also 14.9 External
links and references
[edit] Has it been noted? Formally a Turing machine M is a tuple (Σ,Γ,
Q, δ) where Σ,Γ,Q are finite nonempty sets with Σ Ç Γ and b G Γ − Σ.
The state set Q contains three special states q0,qaccept,qreject. The
transition function δ satisfiesδ : (Q − {qaccept,qreject}) × Γ → Q × Γ
× {−1,1}If δ(q, s)=(q ,s ,h) the interpretation is that if M is in
state q scanning the symbol s then q is the new state, s is the symbol
printed, and the tape head moves left or right one square depending on
whether h is -1 or 1.We assume that the sets Q and Γ are disjoint.A
configuration of M is a string xqy with x, y G Γ∗, y not the empty
string,and q G Q.The interpretation of the configuration xqy is that M
is in state q with xy on its tape, with its head scanning the left-
most symbol of y.If C and C are configurations, then CM→ C if C = xqsy
and δ(q, s) =(q ,s ,h) and one of the following holds:C = xs q y and h
= 1 and y is nonempty.
--------------------------------------------------------------------------------
C = xs q b and h = 1 and y is empty.C = x q as y and h = −1 and x = x
a for some a G Γ.C = q bs y and h = −1 and x is empty.A configuration
xqy is halting if q G {qaccept,qreject}. Note that for each non-
halting configuration C there is a unique configuration C such that
CM→ C .The computation of M on input w G Σ∗is the unique sequence
C0,C1, ... of configurations such that C0 = q0w (or C0 = q0b if w is
empty) and CiM→ Ci+1for each i with Ci+1 in the computation, and
either the sequence is infinite or it ends in a halting configuration.
If the computation is finite, then the number of steps is one less
than the number of configurations; otherwise the number of steps is
infinite. We say that M accepts w iff the computation is finite and
the final configuration contains the state qaccept.
--------------------------------------------------------------------------------
--Musatov
[edit] Problematic sentences Hi,
I find this language a bit problematic:
Given a specific algorithm, one can often show that it must halt for
any input, and in fact computer scientists often do just that as part
of a correctness proof. But each proof has to be developed
specifically for the algorithm at hand; there is no mechanical,
general way to determine whether algorithms on a Turing machine halt.
However, there are some heuristics that can be used in an automated
fashion to attempt to construct a proof, which succeed frequently on
typical programs. This field of research is known as automated
termination analysis. Namely, there is a mechanical way to prove the
termination for exactly those algorithms that can be proven by such a
(finite-length) mathematical proof: Generate all such proofs up to a
given length (the limit can be set arbitrarily high, higher than any
human could hope to do) and check them for correctness. If a proof has
been found, the algorithm does indeed terminate; if not, no such proof
exists and could not been found by a human either. Hence a human is
not "stronger" in this sense than a purely mechanical Turing machine.
Also WTF does the "See also: Watchdog timer" do here :D --SLi (talk)
21:46, 30 March 2009 (UTC)
The quote simply says, "there is no mechanical, general way to
determine whether algorithms on a Turing machine halt". It is true
that if the computation does halt you can tell this; but if it does
not halt there is no general way to determine so by mechanical means
(it may not be provable from a given set of axioms that the program
does not halt). The quote above does not say there is no mechanical
way to search for a proof that a program halts. — Carl (CBM · talk)
22:04, 30 March 2009 (UTC) Somehow it seems like it says that there
may be a "specific" way of proving some algorithm halts, while my
argument is that if there is such a proof that a given Turing machine
always halts, it can be found by an entirely general algorithm, not
"specific" to the "algorithm at hand" (and certainly not only by a
computer scientist). That's what disturbs me in this language. --SLi
(talk) 22:27, 30 March 2009 (UTC) Your argument shows how to find the
proof, but the proof that your argument finds will still be specific
to the algorithm in question (although this "specificity" may seem
trivial). However, when computer scientists actually prove that some
algorithm always terminates, they don't use an exhaustive search for a
proof, they use some ad hoc argument, maybe involving loop invariants
or something like that. Maybe the "has to be" could be changed to
"is". — Carl (CBM · talk) 22:35, 30 March 2009 (UTC) Yes, the proof is
specific to the algorithm, unless you consider it a proof that the
Turing machine that computes and checks those proofs terminates when
given the algorithm. However if interpreted that way, the second part
of "But each proof has to be developed specifically for the algorithm
at hand; there is no mechanical, general way to determine whether
algorithms on a Turing machine halt" seems, while true, misleading
when combined with the first part, since theoretically the developing
of the proof can be done entirely mechanically. --SLi (talk) 22:47, 30
March 2009 (UTC) It's not completely clear to me that an exhaustive
search for a proof counts as "developing" the proof. In any case, when
people in computer science prove that algorithms terminate, they do
not do so by making an exhaustive search for a proof (people don't
prove mathematical theorems that way, either). The usual CS way of
proving algorithms terminate is to do an ad hoc analysis of the
algorithm at hand and write a custom proof for that situation. So if
you want to change "has to" to "is", that seems OK. But I don't
believe the current language is actually inaccurate, since it could be
argued that the exhaustive search does count as "developing" a proof,
and nobody does exhaustive search anyway. And the text does not claim
that it is impossible to search for a proof, only that there is no
mechanical way to separate halting programs from non-halting programs.
— Carl (CBM · talk) 01:39, 31 March 2009 (UTC) Of course exhaustive
search is not how it's done in reality, but then people don't write
their algorithms in Turing machines either. Fast or slow is so far
removed from the topic of this article, it's mostly just about whether
it can be done in finite time by a Turing machine or not (especially
since we are talking about the halting problem). The Turing machine
model is so far from actual reality that I'm afraid bringing in people
proving that an algorithm always halts in such a context only serves
to confuse the reader into thinking it's something that a person can
do but a Turing machine, as a computational model (not as a concrete
machine) cannot. I'll try to think if I could come up with some less
confusing language. --SLi (talk) 01:49, 31 March 2009 (UTC) [edit] The
proof is invalid The halting proof diagnolization argument implies an
algorithm that simulates an input machine on it's own encoding. This
is the realization of "diagonolization". This algorithm takes one
input, copies it, and then gives the original input code the copy as
input. It must do so in order to ensure that the program runs only on
itself. The article calls this machine G.
Because of the fact that the halting algorithm needs algorithm "code"
and input to that code, it is necessary that the halting algorithm
traces the input machine to some degree. It must be traced a certain
amount in order for it to gain meaningful information. I claim that
the amount required ensures it would trace it through the action of
copying the input and running H in the case of Machine G.
So, G recieves (G) as input. (G) is the code of G. G copies the (G)
and gives (G)(G) to the halting algorithm. The halting algorithm
traces G on (G). And we are back where we started - an infinite loop.
This is the reason for the contradiction arrived at, not the
existability of a halting algorithm. —Preceding unsigned comment added
by 96.32.188.25 (talk) 22:25, 18 May 2009 (UTC)
WRONG again. See refutations of the argument presented by similar anon
contributors at Talk:Halting_problem/
Archive3#Article_Halting_proof_fails (March 2009),
Talk:Halting_problem/Archive3#proof_fails (November 2008).
Talk:Halting_problem/Archive3#Proof_is_invalid. (August 2007),
Talk:Halting_problem/Archive1#Big_Trouble_in_Proof.3F (2002) — Arthur
Rubin (talk) 22:40, 18 May 2009 (UTC)
What if You traced state of variables (not constants, stack ...) at
each position (instruction) of program. If that state at certain
position repeated You have found infinite program. But only if You can
trace these things, otherwise I do not know. But if You can Halting
problem is solvable. Of course running program which never halts and
waiting for it to halt is BS ;). You'll wait forever. 84.16.123.194
(talk) 08:53, 26 May 2009 (UTC) Only question is whether You can
create such program that never finishes. Like enumeration of natural
numbers, but of course no overflow is considered here. Also program
which rewrites itself may be a problem on infinite(!) tape. i = 1 ;
while ( i < INFINITY ) { print i ; i := i + 1 } // if i never
overflows => program never halts ; // comparing to INFINITY might be
problem? i = 1 ; while ( 0 < i ) { print i ; i := i + 1 } // this'd
work ;) I have seen some "proofs" of tested program call the testing
program, WTF is that? Why should tested program know about him? I
think that presuming such knowledge is trap. It may be valid program,
but it is quite a special case. Although the other program might be
calling arbitrary programs (on arbitrary addresses, so that he may
find tester) on a tape IRL and run tested program ... I feel (=> don't
have proof), that making one program call other program, which then
calls first one, just for sake of creating recursion is not valid at
all. If I'd create testing program I'd be sure not to let the tested
program know about tester, otherwise there's gonna (might => going
to :) ) be circle and that is what I do not want. To me turings
"proof" is interesting thing to consider when making testing program,
nothing more. AMIRITE? Also it is quite paranoid because You may not
know even IRL whether other program inside tested won't call tester,
or whether some machine bug won't do that :). It is quite similar to
paranoia in Ken Thompson's lecture ;) . 84.16.123.194 (talk) 09:30, 26
May 2009 (UTC) [edit] Artificial Intelligence and the Halting Problem
I'm surprised that there isn't even a paragraph on the use of the
Halting Problem in the philosophy of AI to discriminate (rightly or
wrongly) between what computers and humans can/can't do. —Preceding
unsigned comment added by 121.45.215.163 (talk) 11:05, 16 July 2009
(UTC)
If there is a reliable, mainstream source that discusses it, then by
all means put it into the article. But since neither computers nor
humans can solve the halting problem, it doesn't appear initially that
the halting problem would separate the two. — Carl (CBM · talk) 11:13,
16 July 2009 (UTC) Afraid I don't know the precise reference - but I'm
pretty sure that Roger Penrose covered it in The Emperor's New Mind -
actually, WP discusses it in his article -
http://en.wikipedia.org/wiki/Roger_Penrose#Physics_and_consciousness -
but doesn't give the reference either. —Preceding unsigned comment
added by 121.45.215.163 (talk) 12:33, 16 July 2009 (UTC) We could
probably add a sentence pointing to Roger Penrose, but it's important
to remember that his theories about mathematical philosophy are
somewhat idiosyncratic and don't have broad consensus in the field. So
Penrose's opinions need to be attributed directly to him when they are
presented. — Carl (CBM · talk) 12:37, 16 July 2009 (UTC) There has
been extensive discussion of the issue in the mainstream philosophical
and cognitive-science literature. I believe that Dennett addresses the
matter in Kinds of Minds, for example, and does so not as a new issue
but as an oh-well-I-suppose-I-have-to-discuss-this-old-chestnut thing.
It is my impression that Gödel's incompleteness theorem is more often
invoked in this context than are any undecidability results. The
section Mechanism_(philosophy)#Gödelian_arguments gives a number of
references, some of which probably discuss undecidability results, at
least in passing. —Dominus (talk) 13:06, 16 July 2009 (UTC) [edit]
Using randomness to solve halting problem We know for a fact that a
deterministic machine cannot solve the halting problem in all cases,
but can a probabilistic machine (such as a quantum computer) solve it?
I found a paper that states that one can:
http://arxiv.org/pdf/quant-ph/0512248 (If this link goes dead, please
update it or at least e-mail me a nasty letter. I hate dead links!)
Joeyadams (talk) 04:34, 30 July 2009 (UTC)
Well, I suppose there are various things you could mean by that, but
in the most obvious interpretation, no, it's not possible. The cone of
Turing degrees that compute the halting problem has Lebesgue measure
zero. (Actually if I remember right, all nontrivial Turing cones are
Lebesgue null.) So suppose you had some program with a slot for a true-
random-number generator, and for any input Turing machine, this
program would tell you, correctly with probability 1, whether the TM
halts or not. Then intersecting the sets of streams from the RNG that
work for each particular TM, of which there are only countably many,
you get that for almost all random streams, this program witnesses
that the halting problem is Turing reducible to that stream. But this
is a contradiction. --Trovatore (talk) 07:11, 30 July 2009 (UTC) Yes,
you remember right, for any noncomputable real X the set of reals that
compute X is measure 0. This is due to Sacks in the 1960s. — Carl (CBM
· talk) 13:14, 30 July 2009 (UTC) Re Joeyadams: You have to be
extremely careful with terminology. First, the thing that is
ordinarily called quantum computing is not probabilistic: it is
completely deterministic. However, apparently Kieu is not using the
standard definition of quantum computing, he is using his own idea for
a hypercomputation system and calling it quantum computing. Such
misuse of terminology is unfortunately common among the
hypercomputation community: they often make up new definitions for
standard terms, making it easy to get the wrong impression from
scanning their abstracts. Second, the paper you cited explains that
Kieu's system cannot work. Not only does it depend on a false theorem
about physics, but even if this could be fixed, the method does not
guarantee that the output answer is correct, and so does not actually
decide anything. We do list it on our article on hypercomputation,
though. — Carl (CBM · talk) 13:03, 30 July 2009 (UTC) It is widely
believed and current work indicates that quantum computers do not
alter the notion of computability, and would not solve the halting
problem. The deterministic/probabilistic distinction in the first post
doesn't impact on the halting problem. There are people working on
unphysical models of computation that could solve the problem, but
being unphysical they're not very useful practically (the
hypercomputation mentioned above). There are merely of theoretical
interest. Verbal chat 14:13, 25 September 2009 (UTC) [edit] Modern
Proof Since the original proofs of this involve useless terminology
from recursive function theory, and since the proof is trivial, it is
a shame to use the terminology. Previous discussions of this subject
have been hampered by a lack of consensus about what constitutes
original research in scientific articles. I hope the discussion of
this can follow the WP:ESCA guidelines.Likebox (talk) 00:33, 15
October 2009 (UTC)
Why isn't recursive function theory "modern"? It's a shame to
introduce unusual terminalogy, such as Quineing, to replace perfectly
straightforward recursive function theory. — Arthur Rubin (talk)
00:48, 15 October 2009 (UTC) You are not adressing the input issue.
Nobody nowadays states the halting problem the way it is stated here.
In particular, the input is a complete red-herring.Likebox (talk)
00:50, 15 October 2009 (UTC) [edit] Input nonsense The presentation of
the halting problem is unfortunate, because it pretends that the input
to the program is important in some way. The problem of determining
which programs halt with 0 input is just as undecidable as the problem
of determining which programs halt with arbitrary input. The only
reason the input is mentioned at all is because historically, Turing
proved the theorem by putting the program code on the input stream.
That's not necessary at all, the program can include its own code
internally.Likebox (talk) 00:39, 15 October 2009 (UTC)
That's true, in a sense. But your methodology seems to be to replace
simple diagonalization by complex Quining, which doesn't strike me as
productive. — Arthur Rubin (talk) 00:50, 15 October 2009 (UTC) I see.
But it's a question: quining can be proved by diagonalization, and
diagonalization is equivalent to quining. It's a question of taste. I
think that quining makes the proof more self evident, because it
doesn't involve the input stream. I saw someone get awfully confused
about proving the following theorem: It is undecidable to show that P
halts in polynomial time with arbitrary input. The reason is that the
Turing method passes the code on the input stream. It's an awful
presentation nowadays.Likebox (talk) 00:52, 15 October 2009 (UTC)
Diagonalization is simpler; even in this context where some coding is
required. The term "Quining" is obscure, even with respect to what you
call "modern" methodology. In fact, in your "modern proof" section,
you note that "quining" is necessarily the correct term. Why not use a
method which is correct? Even if the absence of input is the
"correct", "modern" formulation, "Machine R with input T" can be coded
as 1.Write "T" 2.Execute "R" This is clearly computationally
equivalent, so that, if the proof is simpler in the input formulation,
it can easily be translated. — Arthur Rubin (talk) 01:02, 15 October
2009 (UTC)
Indeed, if you formalize what you just said, you prove that quines can
be written. It's a question of whether the self-reference is acheived
by diagonalization, or by the quining result, which makes self-
reference obvious. It's a matter of taste, and I think that both
presentations can be placed side-by-side.Likebox (talk) 01:12, 15
October 2009 (UTC) Only if modern formulations use the word "quine",
and if you can formalize the concept (not the same as "quine") of a
program R' which writes the code of "R" and then executes "R" on that
input. That's not the same as a "quine", which seems to be a program R
which writes its own code. — Arthur Rubin (talk) 01:34, 15 October
2009 (UTC) We seem no longer to have an article on the concept
formerly known as quining; indirect self-reference doesn't seem to
actually use the word, other than as a natural language example. It's
no longer in the text. The article quine (computing) doesn't really
seem applicable, unless modified to include a code of the Turing
machine program as source code. — Arthur Rubin (talk) 01:39, 15
October 2009 (UTC) quine (computing) is Ok. The method of writing
quines makes it obvious that a program can print its own code in a
subroutine, and then go on to do something else. There is no issue
with this particular idea. Modern formulations use the word "fixed
point theorem" which is essentially a synonym for quine.Likebox (talk)
01:43, 15 October 2009 (UTC) [edit] Reverting the changes to the intro
If you don't like quining, discuss that. The old intro is ridiculous,
because the halting problem is never stated about programs with inputs
nowadays. It is always stated about programs without inputs.Likebox
(talk) 00:56, 15 October 2009 (UTC)
No, I don't like quining, and I dispute your statement that "the
halting problem is never stated about programs with inputs nowadays".
Furthermore, even if it were, diagonalization is simpler than quining,
and better understood — at least, by everyone other than yourself with
whom I've interacted. Please stop adding nonsense to the lede. —
Arthur Rubin (talk) 01:02, 15 October 2009 (UTC) If you think that,
just get rid of the quining and we'll discuss it. But please don't
revert the intro--- the intro is stating the halting problem, which is
stated without inputs. You can keep the intro without inputs, and add
a sentence saying "Turing's original formulation was for programs with
inputs, so determining whether a program P with input I halts is
undecidable". But the modern statement of the problem definitely does
not involve inputs in any way, and it is slightly misleading to
present it with inputs. The only purpose of doing it this way is to
avoid quining.Likebox (talk) 01:07, 15 October 2009 (UTC) Also, in my
experience, everyone I have ever met understands quining better than
diagonalization, although in this case both are sufficiently trivial
and sufficiently obviously equivalent that they are
indistinguishable.Likebox (talk) 01:13, 15 October 2009 (UTC) It looks
like a whole section is also being reverted by Arthur Rubin titled
"Modern Proof of Undecidability". It's time for a third party to look
into this issue. Varks Spira (talk) 01:15, 15 October 2009 (UTC) I
just added that section--- Arthur Rubin is not reverting any long-
standing material. This dispute has happened before, and honesty
compels me to admit that consensus swung against "modern proof". I was
hoping that the issue can be looked at again, as a test-case for the
proposed WP:ESCA guidelines. These allow streamlined modernized proofs
in scientific or mathematical articles, in cases where the proofs are
correct, and are only designed to illuminate intermediate steps in
well-understood sourced arguments.Likebox (talk) 01:19, 15 October
2009 (UTC) How do the reliable sources state it? We should follow the
sources, rather than debate the best way to present it. Finell (Talk)
01:22, 15 October 2009 (UTC) This is why I brought up WP:ESCA. There
are sources, and there are sources. The result is so old by now, that
sources discuss it in ten-thousand different ways. In such cases,
using verbatim quotes from sources can be misleading at times. Current
textbooks do usually state the halting problem with the input. But
they also later prove that the halting problem is equally undecidable
without the input. Both theorems are so closely related, that they are
both called "the halting problem", but since the no-input result is
infinitesimally stronger (whatever that means in this case), the no-
input theorem is what people use. The usual path in mathematics
textbooks is to prove the halting problem with input by
diagonalization, then to pass to the no-input case by the Kleene fixed-
point theorem. The Kleene fixed point theorem is equivalent to the
existence of quines, so I just wrote it in this language. According to
WP:ESCA, which I agree with, it is not a good idea to only debate in
terms of the language in sources, because then you can end up with an
illegible mess. Instead, you should consider clarity of explanation
and correctness when talking about objective material that fills in
intermediate steps in proofs. But even with WP:ESCA, it's a judgement
call. So take the time to think about it, and see how the new material
feels.Likebox (talk) 01:29, 15 October 2009 (UTC) [edit] See WT:MATH
See WT:MATH#Halting problem and Likebox. Your input is welcome there,
but I doubt the quined proof would be. — Arthur Rubin (talk) 01:18, 15
October 2009 (UTC)
[edit] Previous Likebox discussions Can be found at Talk:Halting
problem/Archive3#Formal statement redux, Talk:Halting problem/
Archive3#What Is A Rigorous Proof? (November 2007), and Talk:Halting
problem/Archive3#Likebox edits (March 2008). I see no indication that
anyone agreed with Likebox then, nor do I see any likelyhood that
other editors will do so now. — Arthur Rubin (talk) 01:28, 15 October
2009 (UTC)
Things have changed since then, and we have different ideas about how
scientific and mathematical articles should be written. To give a good
test of the proposed guidelines in WP:ESCA, I am bringing this up
again.Likebox (talk) 01:31, 15 October 2009 (UTC) WP:CONSENSUS can
change, but you have provided no evidence that it has, nor that
WP:ESCA (even if a guideline, which it appears not to be; and, in
fact, you are the only one in support in the poll) would provide a
different result. — Arthur Rubin (talk) 01:54, 15 October 2009 (UTC) I
am testing the waters. I am not the only supporter of WP:ESCA, there
are also the authors of the proposed guideline. It is important that
we get this trivial stuff straight, so that mathematical and
scientific articles can be written without the fear of
deletion.Likebox (talk) 02:08, 15 October 2009 (UTC) You have tested
the waters before... Regardless what WP:ESCA says, we write all of our
articles in a way that agrees with the presentations in the mainstream
literature, rather than inventing our own organizational frameworks. —
Carl (CBM · talk) 02:29, 15 October 2009 (UTC) And I will test the
waters again, until this is accepted. It is not reasonable that
material which is clear and correct, old and well-established, can be
removed just because some editors think it sounds too quirky.Likebox
(talk) 20:02, 15 October 2009 (UTC) It isn't "clear" (notation), old,
or (well-)established. Unless you can provide reliable sources which
use the term "quining" for the standard diagonal argument, it
shouldn't be in Wikipedia. I think it's time for a user RfC; Likebox
is saying he intends to violate Wikipedia guidelines in order to get
his material in place. — Arthur Rubin (talk) 20:22, 15 October 2009
(UTC) (deindent) You don't need a formal RfC--- I have made an
attempt, and until you decide to stop getting in the way, then this
attempt will fail. The proof of the Halting problem is not made that
much simpler by Quines, the change is only slight and superficial. But
the Quine method is easy to internalize, and allows simple self-
contained demonstrations of other results in logic which have been
historically more difficult to understand.
I will try again when there are new people here. I intend to continue
to try to incorporate the material, because there are still many
recursion theorists whose work has been badly misinterpreted and will
never see the light of day until these types of expositions are not
censored.Likebox (talk) 21:19, 15 October 2009 (UTC)
Perhaps a formal RfC would be helpful. It might be better if you had a
formal request to get consensus before adding your quirky material to
Wikipeida articles. If you'll agree to that, under penalty of block,
then I don't see a need for a formal RfC. After all, you've done this
at least three times, getting no support from any other editor, as far
as I can tell. It might be helpful, anyway. There's another editor
starting with L to whom I am trying explain the concept of
"consensus", and he doesn't seem to get it. If you interpret
"consensus" the same way he does, you would keep adding the material
until two editors reverted you. — Arthur Rubin (talk) 21:35, 15
October 2009 (UTC) "Lack of consensus" in this case has meant that you
and CBM oppose the additions. The Godel's theorem additions were
stable for months a few years ago, and once you and CBM are
outnumbered, then the additions will be ok again.Likebox (talk) 22:53,
15 October 2009 (UTC) Likebox, you said above "The proof of the
Halting problem is not made that much simpler by Quines,..." As I keep
pointing out, there is no Quine at all in your proof. At least in this
version. What is in your proof is a fixed point obtained from Kleene's
recursion theorem; this fixed point is not a Quine. However, the proof
presented in the article already is more elementary, as it does not
use the recursion theorem at all. So your proof adds additional
complexity compared to the standard proof that was already presented,
which relies only upon the universality of the programming language. —
Carl (CBM · talk) 23:32, 15 October 2009 (UTC)
You say "fixed point" I say "Print your own code". The question of
clarity is whether "fixed point" is a good way of saying "print your
own code". They are logically equivalent, of course. The problem is
that "Fixed point" puts the code of the program on the input stream.
This can be confusing for some people, and I have seen this happen in
real life. The reason is that there is only one input stream for a
Turing machine. You can code up multiple input streams, but that
requires an additional layer of coding. If you just do things in the
most simple-minded way, then the real input of the program is mangled
together with the code of the program, because they both have to fit
on the same stream. This is a manifestation of the practical
limitations of Turing machines. They are universal, of course, so this
is only a practical limitation, but human beings have finite
imagination. If you make the hardware sufficiently primitive and
unforgiving, even the simplest code is a headache to understand. To
show you how this can be a problem, consider the following question:
Is it undecidable whether a program P halts in polynomial time? To
prove that it is in fact undecidable, for contradiction assume that
there is a code POLYNOMIAL which solves the problem, so that POLYNOMIAL
(P) returns "polynomial time" whenever program P acting on input I
runs in polynomial time. Now write SPITE to take input I and do the
following: 1.Print its code into a variable R 2.Compute POLYNOMIAL(R)
3.If the answer is POLYNOMIAL, run some exponential time algorithm on
I, otherwise run any well-known polynomial time algorithm on I. The
contradiction is obvious when written this way. The point is that
POLYNOMIAL is running with "R" as input, while SPITE is running with
"I" as input. So the input to POLYNOMIAL is the fixed size object R,
independent of I. On the other hand, if you try to use the fixed point
theorem, you run into a stupid problem. The input I gets mangled with
the code of SPITE when you use the fixed point theorem. So if the code
"POLYNOMIAL" runs in non-polynomial time, when you fixed-point the
thing with input I, you might end up running in non-polynomial time.
The problem is that the fixed-point theorem doesn't separate the "code
stream" from the "input stream" into two streams. You could easily
reprove the fixed point theorem to do that, of course, but I have seen
a logician get confused with this exact theorem in this exact way. The
point is that the usual terminology is not sufficiently computer-
science friendly to include simple ideas like multiple streams and
separate variables in a natural way. So by restating the theorem using
"print your own code", the pedagogy is simplified considerably,
especially when regarding less trivial proofs. This comes at the
expense of introducing a not completely obvious idea--- that a
computer program can print its own code. By writing things in terms of
"fixed point theorem", the same idea is expressed in a not completely
clear way, for reasons I have explained above.Likebox (talk) 00:05, 16
October 2009 (UTC) My point was simply that there is no Quine
whatsoever in the proof you had added here. You continue to use that
term incorrectly to refer to fixed points in general, when a Quine is
a very specific type of fixed point. — Carl (CBM · talk) 00:19, 16
October 2009 (UTC) I did not use the word "QUINE" anywhere in the text
above. I also did not use the word quine in the addition to this
article, except as an aside, saying "a code which prints out its own
code is called a Quine". This dispute is not over the precise meaning
of the word "Quine". This dispute is over whether you can describe the
proofs of these theorems in common english, as opposed to
jargon.Likebox (talk) 00:42, 16 October 2009 (UTC) No, the dispute is
as to: 1.Whether "Quine" is used in the literature, 2.Whether "write
your own code" is meaningful in a proof (without a proof that it can
be done), and whether that's different from the usual diagonalization
3.Whether your so-called "common English" is sufficiently accurate to
contain the essence of the proof. — Arthur Rubin (talk) 02:29, 16
October 2009 (UTC) This is a question of background and experience. To
construct a quine in a programming language is an exercise for
computer science freshmen. Since I don't use the word quine, your
obsession with it is ridiculous. If you want a proof that any program
X in a random access machine with a variable R can print its code into
this variable, it's simple. It's not different than the usual
diagonalization in any way, except it is conceptually clearer for many
people.Likebox (talk) 04:23, 16 October 2009 (UTC) It may be
"conceptually clearer", but it's more difficult to do correctly than
most diagonalziation arguments. — Arthur Rubin (talk) 06:56, 16
October 2009 (UTC) The proof in the article uses only extremely
elementary properties of the model of computation (and lists the
properties it uses). Your proof requires not only these things, but
also previous knowledge about how to construct fixed points. So I
don't see that your proof is actually simpler. As your proof uses
fixed points for a result where simple diagonalization is all that is
required, I don't see that your proof is conceptually clearer either.
— Carl (CBM · talk) 10:45, 16 October 2009 (UTC) I agree that it is
slightly more involved, but this comes with a great improvement: any
simple undecidability argument does not need to cause confusion with
the input stream. The fixed point theorem proves that a program can
print its own code, just as it proves that the Halting problem without
input is identical to the halting problem with input. The essential
point is that the conceptual content of the fixed point theorem is
"print your own code". This is not stated clearly, and this stuff is
confusing to a lot of people. I did not remove any existing
discussion, I only added text. I have no issues with the fixed point
argument and the diagonalization, I did not challenge them or erase
them. I just added material.Likebox (talk) 20:43, 16 October 2009
(UTC) [edit] Mathematical problems as Halting problem. I like to be
added that certain well known mathematical problems can be expressed
as Halting problem.
These are (among many others):
Goldbach conjecture The existence of odd perfect numbers Fermat Last
Theorem Four Color Problem As opposed that certain problems can not be
expressed as Halting problem, such as the existence of infinite prime
twins. —Preceding unsigned comment added by Lkruijsw (talk • contribs)
16:06, 16 October 2009 (UTC)
I think that has to do with where the conjecture fits in the
arithmetic hierarchy Goldback conjecture is The non-existence of odd
perfect numbers would be Fermat's Last Theorem is Four Color Theorem
is (the coloring is a bounded quantifier) The existence of infinitely
many twin primes would be — Arthur Rubin (talk) 19:28, 16 October 2009
(UTC) Your comment is not clear. Do you propose something? The current
article lacks any illustration as I suggested. Also, the sequence of
understanding is (for me at least): Someone plays with certain
problems, like I mentioned. He realizes that they are Halting
problems. He realizes that not all of them are Halting problems. He
realizes something like 'arithmetic hierarchy'. It is not the other
way around. Starting with a arithmetic hierarchy, from nowhere. And
then one year later finding the examples and fitting it in this
classification. So, from a didactically point of view, this sequence
of human understanding must be followed. BTW, it is Goldbach,not
Goldback. Lkruijsw (talk) 20:51, 16 October 2009 (UTC) I'm sorry,
perhaps I wasn't clear — I was attempting to explain which problems
can be reduced to a halting problem. The halting problem, itself is
("lightface") , as it can be written: "There exists a (finite)
computation (which can be coded as a single number) starting with the
specified initial condition, which terminates." Perhaps the fact that
any problem can be coded as a specific halting problem, and hence any
problem can be coded as a specific "this computation does not halt"
problem, should be noted in this article or in arithmetic hierarchy. —
Arthur Rubin (talk) 10:01, 17 October 2009 (UTC) I agree that the
natural examples of complete sets at various levels of the
arithmetical hierarchy should be mentioned in that article, and that
some examples of natural and sets should be mentioned here. On the
other hand, we have to be precise anytime we say "reduced" in an
article, since the sets that are Turing reducible to the halting
problem are exactly the sets. — Carl (CBM · talk) 14:27, 28 October
2009 (UTC) [edit] text th@ may likely be deleted by someone with an
unwholesome interest in p=/=np <!DOCTYPE html PUBLIC "+//W3C//DTD HTML
4.01//EN" "http://www.w3.org/TR/html4/strict.dtd"> <html><head> <meta
http-equiv= "Content+Type" content= "text/html; charset= iso+8859+1">
<title>ERROR: The requested URL could not be retrieved</title> <style
type= "text/css"></style> </head><body>
ERROR The requested URL could not be retrieved
--------------------------------------------------------------------------------
Invalid Request error was encountered while trying to process the
request:
GET http://www.meami.org/?cx= 000961116824240632825%3A5n3yth9xwbo&cof=
FORID%3A9%3B+NB%3A1&ie= UTF-8&q= +Suggestions++Close+Sign+in+United
+States+-+English++Argentina+%28Espa%F1ol%29+Brasil+%28Portugu%EAs
%29+Canada+%28English%29+Canada+%28Fran%E7ais%29+%26%2320013%3B
%26%2322269%3B+%28%26%2331616%3B%26%2320307%3B%26%2320013%3B
%26%2325991%3B%29+Colombia+%28Espa%F1ol%29+Deutschland+%28Deutsch
%29+Espa%F1a+%28Espa%F1ol%29+France+%28Fran%E7ais%29+India+%28English
%29+Italia+%28Italiano%29+%26%2326085%3B%26%2326412%3B+
%28%26%2326085%3B%26%2326412%3B%26%2335486%3B%29+%26%2354620%3B
%26%2344397%3B+%28%26%2354620%3B%26%2344397%3B%26%2350612%3B%29+M
%E9xico+%28Espa%F1ol%29+Per%FA+%28Espa%F1ol%29+%26%231056%3B
%26%231086%3B%26%231089%3B%26%231089%3B%26%231080%3B%26%231103%3B+%28P
%26%231091%3B%26%231089%3B%26%231089%3B%26%231082%3B%26%231080%3B
%26%231081%3B%29+%26%2321488%3B%26%2328771%3B+%28%26%2332321%3B
%26%2339636%3B%26%2320013%3B%26%2325991%3B%29+United+Kingdom+%28English
%29+United+States+%28English%29+More...+%5Bmicrosoft+developer+network
%5D+HomeCurrent+IssueTopicsIssuesColumnsDownloadsSubscribe+Magazine+%3E
+Issues+%3E+2004+%3E+March+%3E++The+ASP+Column%3A+Using+SOAP+Extensions
+in+ASP.NE...+The+ASP+Column+Using+SOAP+Extensions+in+ASP.NET+George
+Shepherd++Code+download+available+at%3A+ASPColumn0403.exe+%28136+KB
%29+Browse+the+Code+Online++Contents+Web+Services+and+ASP.NET+Chaining
+the+Message+Stream+Life+of+the+SOAP+Message+Processing+the+Message
+Deploying+via+Web.config+The+SoapExtensionAttribute+Class+Debugging
+the+Extension+Conclusion++It%27s+useful+to+be+able+to+make+a+method
+call+from+one+computer+to+another+over+the+Internet.+But+if+things
+stopped+there%2C+Web+services+would+be+a+dead+end.+The+ASP.NET+SOAP
+extension+framework+represents+a+means+of+intercepting+SOAP+messages
+and+hooking+your+own+code+into+the+SOAP+message+pipeline.+Through+the
+SOAP+extension+architecture%2C+you+have+access+to+the+message+as+it+is
+deserialized+into+objects%2C+and+as+it%27s+serialized+from+a+common
+language+runtime+%28CLR%29+object+back+into+a+SOAP+message.+In+this
+month%27s+column+I%27m+going+to+take+a+look+at+implementing+SOAP
+extensions+in+ASP.NET.+SOAP+extensions+solve+the+problem+of+performing
+pre-+and+post-processing+of+SOAP+messages.+Some+applications+of+this
+capability+are+obvious.+For+example%2C+if+you+want+to+log+SOAP
+messages+as+they%27re+processed+by+your+Web+site%2C+one+of+the+best
+places+to+do+it+is+within+a+SOAP+extension.+Some+other+applications
+may+not+be+quite+as+obvious%2C+but+are+just+as+useful.+SOAP+extensions
+are+a+means+of+transforming+messages.+If+you+want+to+secure+a+SOAP
+message%2C+you+could+write+SOAP+extensions+that+encrypt+and+decrypt
+messages+coming+across+the+wire.+Finally%2C+the+SOAP+extension
+architecture+represents+a+way+to+embellish+the+SOAP+payload+%28for
+example%2C+by+sending+attachments+with+a+message%29.+In+this+column%2C
+I%27ll+show+you+how+to+write+a+SOAP+extension+that+logs+the+messages
+and+reverses+the+text+going+across+the+wire.+Many+examples+of+SOAP
+extensions+show+how+to+log+the+requests%2C+so+I%27ll+focus+on
+modifying+the+message+stream.+The+example+illustrates+a+starting+point
%2C+and+you+should+see+clearly+how+to+insert+your+own+extension-
processing+code.++Web+Services+and+ASP.NET+Web+services+have+evolved+to
+allow+global+communication+between+computers.+The+software+industry+is
+settling+upon+SOAP+as+a+common+wire+format+and+HTTP+as+the+connection
+protocol.+A+Web+service+is+basically+a+programmable+Web+site+and
+represents+a+universal+remote+procedure+call+mechanism.+ASP.NET+is
+built+around+a+well-defined+pipeline+capable+of+responding+to
+virtually+any+kind+of+HTTP+request.+If+you+think+about+it%2C+a+SOAP
+request%2C+when+bound+to+the+HTTP+protocol%2C+is+just+another+HTTP
+request+%28albeit+one+that+contains+a+SOAP+envelope%29.+Web+services
+fit+cleanly+into+the+ASP.NET+pipeline%2C+which+provides+a+hook+for
+extending+messages.+Figure+1+illustrates+how+SOAP+extensions+fit+into
+the+overall+ASP.NET+architecture.+Figure+1+ASP.NET+Extension
+Architecture++When+a+client+sends+SOAP+messages+to+the+ASP.NET+Web
+service%2C+it+includes+the+name+of+the+method+in+two+places%3A+in+the
+SOAPAction+header+and+the+request+element%27s+name.+By+default%2C
+ASP.NET+uses+the+SOAPAction+header+to+figure+out+which+method+in+the
+class+to+call+%28the+method+must+be+marked+with+the+WebMethod
+attribute%29.+The+handler+uses+.NET+reflection+to+find+the+method+in
+the+class+being+called+by+the+client.+After+figuring+out+which
+WebMethod+to+call%2C+the+handler+deserializes+the+SOAP+message+into
+.NET+objects+that+can+be+supplied+as+method+arguments+during
+invocation.+ASP.NET+automates+much+of+this+process%2C+making+it+very
+easy+to+set+up+and+run+a+Web+service.+However%2C+if+you+want+to+see+or
+modify+the+message+stream+coming+across+the+wire%2C+it%27s+not+exactly
+intuitive+how+to+do+so.+That%27s+where+SOAP+extensions+come+in.
+ASP.NET+SOAP+extensions+are+implemented+by+classes+deriving+from+the
+SoapExtension+class.+They+allow+you+to+intercept+messages+and+modify
+the+corresponding+streams.+You+can+have+a+full-fledged+SOAP+extension
+up+and+running+by+overriding+a+few+simple+functions.+Let%27s+take+a
+look+at+the+SoapExtension+class.+The+basis+of+SOAP+extensions+is+the
+SoapExtension+class.+Fortunately%2C+SoapExtension+has+a+relatively
+small+surface+area.+The+main+methods+of+concern+are+ChainStream%2C
+GetInitializer%2C+Initialize%2C+and+ProcessMessage.+ChainStream
+captures+the+message+stream+within+the+SOAP+call.+GetInitializer+and
+Initialize+provide+a+means+of+initialization.+ProcessMessage+is+the
+heart+of+the+extension+where+most+of+the+development+attention+goes.+I
%27ll+start+the+tour+with+the+ChainStream+method.++Chaining+the+Message
+Stream+Overriding+the+ChainStream+method+allows+you+to+hook+into+the
+message+stream.+When+an+extension+is+installed%2C+ASP.NET+calls
+ChainStream%2C+passing+in+a+reference+to+the+stream+containing+the
+SOAP+message.+The+following+code+is+typical+of+most+implementations+of
+ChainStream%3A++public+override+Stream++++ChainStream%28+Stream+stream
+%29+%7B+++%2F%2F+Save+the+message+stream+in+a+member+variable.++
+_originalStream+%3D+stream%3B++++%2F%2F+Create+a+new+stream+and+save
+it+as+a+member+variable.+++_workingStream+%3D+new+MemoryStream
%28%29%3B+++return+_newStream%3B+%7D++The+main+goal+is+to+save+the
+stream+containing+the+SOAP+message.+This+implementation+also+creates+a
+new+stream+for+holding+a+working+copy+of+the+message.+The+Stream
+passed+into+ChainStream+contains+the+serialized+SOAP+request.+SOAP
+extensions+work+by+writing+into+a+stream.+Notice+that+ChainStream
+creates+a+memory+stream+and+passes+it+back+to+the+caller.+The+stream
+returned+by+ChainStream+contains+the+serialized+SOAP+response.+You
%27ll+see+later+in+this+column+how+to+deploy+the+extension.+For+now%2C
+you+should+just+be+aware+that+this+method+hooks+the+message+stream.+
+Life+of+the+SOAP+Message+Once+an+extension+is+deployed+with+a+project
+and+the+message+stream+is+chained%2C+SOAP+requests+and+responses+start
+to+pass+through+it.+There%27s+a+rather+intricate+lifecycle+to+the+SOAP
+message%2C+involving+multiple+stages+of+message+processing.+These
+stages+are+represented+by+the+SoapMessageStage+enumeration%2C+and+they
+include+BeforeSerialize%2C+AfterSerialize%2C+BeforeDeserialize%2C+and
+AfterDeserialize.+This+chain+of+events+proceeds+in+a+predefined
+sequence.+Extensions+can+be+installed+with+both+the+server+and+the
+client+applications%2C+and+a+similar+sequence+of+events+happens+on
+each+side.+Figure+2+shows+the+path+of+a+SOAP+message+through
+extensions+deployed+on+both+sides.+The+numbers+1-13+indicate+the+order
+in+which+the+stages+are+processed.+Figure+2+Lifecycle+of+a+SOAP
+Request++Understanding+what+happens+at+each+stage+is+key+to+making+the
+extension+work.+During+the+entire+transaction%2C+the+extension+is
+running+on+both+the+client+and+server.+For+example%2C+in+Steps+2+and
+3%2C+the+message+is+being+prepared+on+the+client+as+an+outgoing
+message.+A+more+detailed+description+of+the+processing+stages+follows.
+SoapMessageStage.BeforeSerialize+happens+just+before+the+SOAP+message
+is+serialized.+This+is+Step+2+in+the+diagram.+When+a+SOAP+message+is
+processed+in+client+mode+%28the+SOAP+message+is+outgoing%29%2C+the
+BeforeSerialize+stage+occurs+immediately+after+a+client+invokes+a+Web
+service+proxy+method%2C+but+before+the+message+is+sent+out+over+the
+wire.+When+the+message+is+being+processed+in+server+mode+%28the+SOAP
+message+is+incoming%29%2C+BeforeSerialize+occurs+immediately+after+the
+WebMethod+returns+and+before+the+return+values+are+serialized+and+sent
+back+to+the+client.+SoapMessageStage.BeforeDeserialize+occurs+before+a
+message+is+deserialized+and+turned+into+a+CLR+object.+When+processing
+in+client+mode%2C+BeforeDeserialize+occurs+after+receiving+the
+response+from+a+WebMethod+invocation%2C+and+just+before+the+response
+is+deserialized+into+a+CLR+object.+When+processing+in+server+mode%2C
+BeforeDeserialize+occurs+after+a+SOAP+message+is+received+by+the+Web
+server%2C+but+before+the+SOAP+message+is+deserialized+into+objects+and
+passed+as+arguments+to+the+WebMethod.
+SoapMessageStage.AfterDeserialize+occurs+immediately+after+a+SOAP
+message+is+deserialized+into+objects.+When+processing+in+client+mode
%2C+the+AfterDeserialize+stage+occurs+after+the+response+from+the
+WebMethod+invocation+has+been+deserialized+into+an+object%2C+but+prior
+to+the+client+receiving+the+deserialized+results.+When+processing+in
+server+mode%2C+AfterDeserialize+occurs+after+the+request+is
+deserialized+into+objects%2C+but+before+the+method+on+the+object
+representing+the+Web+service+method+is+called.
+SoapMessageStage.AfterSerialize+occurs+just+after+a+SOAP+message+is
+serialized%2C+but+before+the+SOAP+message+is+sent+over+the+wire.+When
+processing+in+client+mode%2C+AfterSerialize+occurs+after+a+client
+invokes+a+WebMethod+on+a+client+proxy+and+the+parameters+are
+serialized+into+XML%2C+and+before+the+SOAP+message+is+sent+over+the
+wire.+When+processing+in+server+mode%2C+the+AfterSerialize+stage
+occurs+after+a+WebMethod+returns+and+values+are+serialized+into+XML%2C
+and+before+the+SOAP+message+is+sent+over+the+network.++Processing+the
+Message+The+heart+of+the+SOAP+extension+lies+in+the+ProcessMessage
+method.+ProcessMessage+is+called+multiple+times.+Figure+3+shows+the
+ProcessMessage+code+for+this+month%27s+example.++Figure+3+Processing
+the+SOAP+Message+Stages++public+override+void++++ProcessMessage
%28SoapMessage+message%29++%7B+++switch+%28message.Stage%29++++%7B+++++
%2F%2F+Incoming+from+client+++++case+SoapMessageStage.BeforeDeserialize
%3A+++++++ReceiveStream%28%29%3B+++++++LogInput%28message%29%3B++++++
+break%3B++++++%2F%2F+About+to+call+methods+++++case
+SoapMessageStage.AfterDeserialize%3A+++++++break%3B++++++%2F%2F+After
+Method+call+++++case+SoapMessageStage.BeforeSerialize%3A+++++++break
%3B++++++%2F%2F+Outgoing+to+other++++++case
+SoapMessageStage.AfterSerialize%3A+++++++LogOutput%28message%29%3B++++
+++ReturnStream%28%29%3B+++++++break%3B++++++default%3A+++++++throw+new
+Exception%28%22No+stage+such+as+this...%22%29%3B+++%7D+%7D++void
+ReturnStream%28%29+%7B+++CopyAndReverse%28_workingStream%2C
+_originalStream%29%3B+%7D++void+ReceiveStream%28%29+%7B++
+CopyAndReverse%28_originalStream%2C+_workingStream%29%3B+%7D++void
+CopyAndReverse%28Stream+from%2C+Stream+to%29++%7B+++TextReader+tr+%3D
+new+StreamReader%28from%29%3B+++TextWriter+tw+%3D+new+StreamWriter
%28to%29%3B++++string+str+%3D+tr.ReadToEnd%28%29%3B+++char%5B%5D+data+
%3D+str.ToCharArray%28%29%3B+++Array.Reverse%28data%29%3B+++string
+strReversed+%3D+new+string%28data%29%3B+++tw.Write%28strReversed%29%3B
+++tw.Flush%28%29%3B+%7D++Notice+that+this+code+simply+switches+on+the
+different+SOAP+message+stages.+I%27m+not+really+concerned+with
+BeforeSerialize%2C+nor+am+I+worried+about+AfterDeserialize+in+this
+case.+BeforeDeserialize+handles+the+including+stream%2C+copying+and
+reversing+the+message%2C+which+is+logged.+The+extension+handles
+AfterSerialize+by+logging+the+message+%28before+reversing+it%29%2C
+then+reversing+the+contents+of+the+stream+before+returning+it+to+the
+client.+I+used+a+TCP+tracing+program+to+watch+the+SOAP+calls+going
+across+the+wire.+Figure+4+shows+the+requests+and+responses.+These+are
+the+actual+bits+as+they+are+transmitted+on+the+wire.+You+can+see+that
+the+SOAP+messages+appear+backward%2C+showing+that+the+SOAP+extension
+worked.++Figure+4+Tracing+SOAP+Messages++HTTP+Request++POST+
%2FUseSoapReverserExtension%2FService1.asmx+HTTP%2F1.1+User-Agent%3A
+Mozilla%2F4.0+%28compatible%3B+MSIE+6.0%3B+MS+Web+Services+Client+
+Protocol+1.0.3705.0%29+Content-Type%3A+text%2Fxml%3B+charset
%3Dutf-8+SOAPAction%3A+%22http%3A%2F%2Ftempuri.org%2FHelloWorld
%22+Content-Length%3A+324+Expect%3A+100-continue+Connection%3A+Keep-
Alive+Host%3A+localhost++%3EepolevnE%3Apaos%2F%3C%3EydoB%3Apaos%2F%3C
%3EdlroWolleH%2F%3C%3EemaNrts%2F%3CegroeG%3EemaNrts%3C%3E%22%2F
+gro.irupmet%2F%2F%3Aptth%22%3Dsnlmx+dlroWolleH%3C%3EydoB%3Apaos%3C%3E
%22amehcSLMX%2F1002%2F+gro.3w.www%2F%2F%3Aptth%22%3Ddsx%3Asnlmx+
%22ecnatsni-amehcSLMX%2F1002%2Fgro.3w.www%2F%2F+%3Aptth%22%3Disx
%3Asnlmx+%22%2Fepolevne%2Fpaos%2Fgro.paoslmx.samehcs%2F%2F%3Aptth
%22%3Dpaos%3Asnlmx++epolevnE%3Apaos%3C%3E%3F%228-ftu%22%3Dgnidocne+
%220.1%22%3Dnoisrev+lmx%3F%3C++HTTP+Response++HTTP%2F1.1+100+Continue
+Server%3A+Microsoft-IIS%2F5.1+Date%3A+Mon%2C+15+Dec
+2003+21%3A02%3A08+GMT++HTTP%2F1.1+200+OK+Server%3A+Microsoft-IIS
%2F5.1+Date%3A+Mon%2C+15+Dec+2003+21%3A02%3A08+GMT+Cache-Control%3A
+private%2C+max-age%3D0+Content-Type%3A+text%2Fxml%3B+charset
%3Dutf-8+Content-Length%3A+371++%3EepolevnE%3Apaos%2F%3C%3EydoB%3Apaos
%2F%3C%3EesnopseRdlroWolleH%2F%3C%3EtluseRdlroWolleH%2F+%3CegroeG+
%2CdlroW+olleH%3EtluseRdlroWolleH%3C%3E%22%2Fgro.irupmet%2F%2F%3Aptth
%22%3Dsnlmx++esnopseRdlroWolleH%3C%3EydoB%3Apaos%3C%3E%22amehcSLMX
%2F1002%2Fgro.3w.www%2F%2F+%3Aptth%22%3Ddsx%3Asnlmx+%22ecnatsni-
amehcSLMX%2F1002%2Fgro.3w.www%2F%2F%3Aptth%22%3Disx%3Asnlmx+%22%2F
+epolevne%2Fpaos%2Fgro.paoslmx.samehcs%2F%2F%3Aptth%22%3Dpaos%3Asnlmx
+epolevnE%3Apaos%3C%3E%3F%228-+ftu%22%3Dgnidocne+%220.1%22%3Dnoisrev
+lmx%3F%3C+++Deploying+via+Web.config+As+with+many+of+the+ASP.NET
+extensibility+points%2C+SOAP+extensions+may+be+configured+in
+web.config.+If+you+mention+the+SOAP+extension+in+your+web.config+file
%2C+ASP.NET+will+use+it+to+process+the+WebMethods+exposed+by+your
+service.+Figure+5+shows+how+to+declare+a+SOAP+extension+in+web.config.
++Figure+5+Declaring+the+SOAP+Extension+in+Web.Config++%3Cconfiguration
%3E+++%3Csystem.web%3E+++++%3CwebServices%3E++++++%3CsoapExtensionTypes
%3E+++++++%3Cadd+type%3D
%22SoapReverserExtensionLib.SoapReverserExtension%2C++++++++
+SoapReverserExtensionLib%22++++++++++++priority%3D%221%22+++++++++++
+group%3D%220%22+%2F%3E++++++%3C%2FsoapExtensionTypes%3E+++++%3C
%2FwebServices%3E++%3C%2Fsystem.web%3E+%3C%2Fconfiguration%3E+++The
+SoapExtensionAttribute+Class+You+may+also+configure+singular
+WebMethods+to+run+with+your+SOAP+extension+by+adorning+the+WebMethod
+with+a+custom+attribute+derived+from+the+SoapExtensionAttribute+class.
+ASP.NET+learns+what+kind+of+extension+to+use+by+querying+the
+ExtensionType+method+of+the+attribute+%28which+returns+the+type+of
+extension+to+load%29.+Figure+6+shows+an+example+of+a+SOAP+extension
+attribute+for+use+with+the+SoapReverserExtension.++Figure+6+Defining+a
+Custom+SoapExtensionAttribute++%5BAttributeUsage
%28AttributeTargets.Method%29%5D+public+class
+ReverserExtensionAttribute+%3A++++SoapExtensionAttribute++%7B++
+private+int+priority%3B+++public+override+Type+ExtensionType++++%7B+++
++get+%7B+++++++%2F%2F+return+type+of+extension+to+load++++++return
+typeof%28ReverserExtension%29%3B++++++%7D+++%7D++++public+override+int
+Priority++++%7B+++++get+%7B+return+priority%3B+%7D+++++set+%7B
+priority+%3D+value%3B+%7D+++%7D+%7D++%2F%2F+Use+the+attribute+like
+this%3A+%5BWebMethod%5D+%5BReverserExtensionAttribute%5D+public+string
+HelloWorld%28string+strName%29+%7B+++return+%22Hello+World%2C+%22+%2B
+strName%3B+%7D++You+can+apply+the+attribute+to+a+particular+WebMethod
+to+configure+the+extension+to+be+used+with+only+that+method+as+an
+alternative+to+configuring+the+extension+through+web.config%2C+as
+shown+in+Figure+6.+This+will+cause+the+extension+to+be+used+for+all
+methods.++Debugging+the+Extension+Debugging+a+SOAP+extension+can+be+a
+bit+different+from+how+you+might+normally+debug+a+Web+service+hosted
+in+ASP.NET.+ASP.NET+uses+the+DefaultWsdlHelpGenerator.aspx+page+as
+configured+in+machine.config+to+display+test+pages+for+your+Web
+services.+These+test+pages+can+be+used+to+invoke+your+WebMethods%2C
+but+the+test+harness+does+this+by+making+HTTP+POST+requests+to+the
+server+rather+than+HTTP+SOAP+requests.+SoapExtensions+only+work+with
+SOAP+requests%2C+and+thus+any+requests+to+your+Web+service+made+using
+the+default+test+page+will+result+in+your+extensions+not+being+used.
+To+debug+the+extension%2C+use+either+a+custom+SoapExtensionAttribute
+or+a+configuration+setting+in+web.config+to+ensure+that+your+extension
+will+be+used+for+the+desired+WebMethod.+Set+any+appropriate
+breakpoints+in+your+extension+code.+Press+F5+to+start+debugging+your
+Web+service%3B+Microsoft%AE+Internet+Explorer+will+load+and+display
+the+test+page+for+your+Web+service.+Now%2C+instead+of+using+the+test
+page+to+invoke+your+Web+service%2C+use+another+Web+service+client+to
+invoke+your+method+using+a+SOAP+request+%28one+such+test+tool+is
+WebServiceStudio%2C+available+from+GotDotNet%29.+When+the+WebMethod+is
+invoked%2C+you%27ll+see+the+debugger+break+on+the+breakpoints+you%27ve
+set.++Conclusion+This+month+I+looked+at+a+way+to+hook+into+the+SOAP
+message+stream+using+ASP.NET.+While+it%27s+sometimes+interesting+to
+take+a+peek+at+the+data+coming+across+the+wire%2C+it%27s+even+more
+useful+to+be+able+to+add+functionality+like+logging%2C+compression%2C
+and+encryption.+The+basic+idea+of+SOAP+extensions+is+to+intercept+the
+message+stream+and+work+with+it+%28encrypting+the+stream%2C+adding+to
+it%2C+and+so+on%29.+The+trick+to+making+it+work+is+to+understand+the
+stages+of+SOAP+message+processing.+And+remember%2C+you+can+write
+extensions+to+work+only+on+the+server%2C+only+on+the+client%2C+or+you
+can+create+them+to+work+on+both+ends.++Send+your+questions+and
+comments+for+George+to++asp-net%40microsoft.com.++George+Shepherd
+specializes+in+software+development+for+the+.NET+Framework.+He+is+the
+author+of+Programming+with+Microsoft+Visual+C%2B%2B.NET+%28Microsoft
+Press%2C+2002%29%2C+and+coauthor+of+Applied+.NET+%28Addison-Wesley%2C
+2001%29.+He+teaches+seminars+with+DevelopMentor+and+is+a+contributing
+architect+for+Syncfusion%27s+.NET+tools.++++%09+%A9+2009+Microsoft
+Corporation.+All+rights+reserved.+Terms+of+Use+%7C+Trademarks+%7C
+Privacy+Statement+%7C+Site+Feedback+Page+view+tracker&sa= Search HTTP/
1.1 Host: www.meami.org User+Agent: Mozilla/5.0 (Windows; U; Windows
NT 5.1; en+US; rv:1.9.1.3) Gecko/20090824 Firefox/3.5.3 Accept: text/
html,application/xhtml+xml,application/xml;q= 0.9,*/*;q= 0.8 Accept
+Language: en+us Accept+Encoding: gzip,deflate Accept+Charset: ISO
+8859+1,utf+8;q= 0.7,*;q= 0.7 Keep+Alive: 300 Connection: keep+alive
Referer: http://meami.org/ Some possible problems are:
Missing or unknown request method.
Missing URL.
Missing HTTP Identifier (HTTP/1.0).
Request is too large.
Content+Length missing for POST or PUT requests.
Illegal character in hostname; underscores are not allowed.
Your cache administrator is <a href= "mailto:webmaster%W">webmaster</
a>.
--------------------------------------------------------------------------------
Generated Fri, 30 Oct 2009 00:14:35 GMT by demil1.byetcluster.com
(Lusca/LUSCA_HEAD) </body></html> <!DOCTYPE html PUBLIC "+//W3C//DTD
XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-
transitional.dtd"> <html xmlns= "http://www.w3.org/1999/xhtml"
xml:lang= "en" lang= "en" dir= "ltr">
<head>
<title>Main Hello World Wide Web 1 and 2 + Complexity classes P and
NP</title>
<meta http-equiv=
"Content+Type" content= "text/html; charset= iso+8859+1"/>
<meta name=
"description" content= "Main Hello World Wide Web 1 and 2 + Complexity
classes P and NP"/>
<meta name=
"KEYWORDS" content= "main hello world wide web 1, main hello world
wide web 2, first world wide web, second world wide web, i, ii,
history, poster, picture, web @ up on, magazine, P = NP, Complexity
classes P and NP, Template: Complexity Classes, 1974, Algorithm,
Binary and text files, Chess, Clay Mathematics Institute,
Computational complexity theory, Computer scientist" /> <meta name=
"meami.org robots" content= "index,follow" /> <link rel= "shortcut
icon" href= "/favicon.ico" />
<script type=
"text/javascript" src= "/history/skins/wikibits.js"></script>
<link rel=
"stylesheet" type= "text/css" href= "/history/stylish.css"/>
</head>
<body leftmargin= "0" topmargin= "0" marginwidth= "0" marginheight=
"0"> <form name= "searchform" action= "a/../Special:Search" id=
"searchform">
ERROR The requested URL may be retrieved In: valid Request err/ or was
en/ countered process request:
GET http://meami.org/?cx=
000961116824240632825%3A5n3yth9xwbo&cof= FORID%3A9%3B+NB%3A1&ie=
UTF-8&q= +Suggestions++Close+Sign+in+United+States+-+English++Argentina
+%28Espa%F1ol%29+Brasil+%28Portugu%EAs%29+Canada+%28English%29+Canada+
%28Fran%E7ais%29+%26%2320013%3B%26%2322269%3B+%28%26%2331616%3B
%26%2320307%3B%26%2320013%3B%26%2325991%3B%29+Colombia+%28Espa%F1ol
%29+Deutschland+%28Deutsch%29+Espa%F1a+%28Espa%F1ol%29+France+%28Fran
%E7ais%29+India+%28English%29+Italia+%28Italiano%29+%26%2326085%3B
%26%2326412%3B+%28%26%2326085%3B%26%2326412%3B%26%2335486%3B%29+
%26%2354620%3B%26%2344397%3B+%28%26%2354620%3B%26%2344397%3B
%26%2350612%3B%29+M%E9xico+%28Espa%F1ol%29+Per%FA+%28Espa%F1ol%29+
%26%231056%3B%26%231086%3B%26%231089%3B%26%231089%3B%26%231080%3B
%26%231103%3B+%28P%26%231091%3B%26%231089%3B%26%231089%3B%26%231082%3B
%26%231080%3B%26%231081%3B%29+%26%2321488%3B%26%2328771%3B+
%28%26%2332321%3B%26%2339636%3B%26%2320013%3B%26%2325991%3B%29+United
+Kingdom+%28English%29+United+States+%28English%29+More...+%5Bmicrosoft
+developer+network%5D+HomeCurrent
+IssueTopicsIssuesColumnsDownloadsSubscribe+Magazine+%3E+Issues+%3E
+2004+%3E+March+%3E++The+ASP+Column%3A+Using+SOAP+Extensions+in
+ASP.NE...+The+ASP+Column+Using+SOAP+Extensions+in+ASP.NET+George
+Shepherd++Code+download+available+at%3A+ASPColumn0403.exe+%28136+KB
%29+Browse+the+Code+Online++Contents+Web+Services+and+ASP.NET+Chaining
+the+Message+Stream+Life+of+the+SOAP+Message+Processing+the+Message
+Deploying+via+Web.config+The+SoapExtensionAttribute+Class+Debugging
+the+Extension+Conclusion++It%27s+useful+to+be+able+to+make+a+method
+call+from+one+computer+to+another+over+the+Internet.+But+if+things
+stopped+there%2C+Web+services+would+be+a+dead+end.+The+ASP.NET+SOAP
+extension+framework+represents+a+means+of+intercepting+SOAP+messages
+and+hooking+your+own+code+into+the+SOAP+message+pipeline.+Through+the
+SOAP+extension+architecture%2C+you+have+access+to+the+message+as+it+is
+deserialized+into+objects%2C+and+as+it%27s+serialized+from+a+common
+language+runtime+%28CLR%29+object+back+into+a+SOAP+message.+In+this
+month%27s+column+I%27m+going+to+take+a+look+at+implementing+SOAP
+extensions+in+ASP.NET.+SOAP+extensions+solve+the+problem+of+performing
+pre-+and+post-processing+of+SOAP+messages.+Some+applications+of+this
+capability+are+obvious.+For+example%2C+if+you+want+to+log+SOAP
+messages+as+they%27re+processed+by+your+Web+site%2C+one+of+the+best
+places+to+do+it+is+within+a+SOAP+extension.+Some+other+applications
+may+not+be+quite+as+obvious%2C+but+are+just+as+useful.+SOAP+extensions
+are+a+means+of+transforming+messages.+If+you+want+to+secure+a+SOAP
+message%2C+you+could+write+SOAP+extensions+that+encrypt+and+decrypt
+messages+coming+across+the+wire.+Finally%2C+the+SOAP+extension
+architecture+represents+a+way+to+embellish+the+SOAP+payload+%28for
+example%2C+by+sending+attachments+with+a+message%29.+In+this+column%2C
+I%27ll+show+you+how+to+write+a+SOAP+extension+that+logs+the+messages
+and+reverses+the+text+going+across+the+wire.+Many+examples+of+SOAP
+extensions+show+how+to+log+the+requests%2C+so+I%27ll+focus+on
+modifying+the+message+stream.+The+example+illustrates+a+starting+point
%2C+and+you+should+see+clearly+how+to+insert+your+own+extension-
processing+code.++Web+Services+and+ASP.NET+Web+services+have+evolved+to
+allow+global+communication+between+computers.+The+software+industry+is
+settling+upon+SOAP+as+a+common+wire+format+and+HTTP+as+the+connection
+protocol.+A+Web+service+is+basically+a+programmable+Web+site+and
+represents+a+universal+remote+procedure+call+mechanism.+ASP.NET+is
+built+around+a+well-defined+pipeline+capable+of+responding+to
+virtually+any+kind+of+HTTP+request.+If+you+think+about+it%2C+a+SOAP
+request%2C+when+bound+to+the+HTTP+protocol%2C+is+just+another+HTTP
+request+%28albeit+one+that+contains+a+SOAP+envelope%29.+Web+services
+fit+cleanly+into+the+ASP.NET+pipeline%2C+which+provides+a+hook+for
+extending+messages.+Figure+1+illustrates+how+SOAP+extensions+fit+into
+the+overall+ASP.NET+architecture.+Figure+1+ASP.NET+Extension
+Architecture++When+a+client+sends+SOAP+messages+to+the+ASP.NET+Web
+service%2C+it+includes+the+name+of+the+method+in+two+places%3A+in+the
+SOAPAction+header+and+the+request+element%27s+name.+By+default%2C
+ASP.NET+uses+the+SOAPAction+header+to+figure+out+which+method+in+the
+class+to+call+%28the+method+must+be+marked+with+the+WebMethod
+attribute%29.+The+handler+uses+.NET+reflection+to+find+the+method+in
+the+class+being+called+by+the+client.+After+figuring+out+which
+WebMethod+to+call%2C+the+handler+deserializes+the+SOAP+message+into
+.NET+objects+that+can+be+supplied+as+method+arguments+during
+invocation.+ASP.NET+automates+much+of+this+process%2C+making+it+very
+easy+to+set+up+and+run+a+Web+service.+However%2C+if+you+want+to+see+or
+modify+the+message+stream+coming+across+the+wire%2C+it%27s+not+exactly
+intuitive+how+to+do+so.+That%27s+where+SOAP+extensions+come+in.
+ASP.NET+SOAP+extensions+are+implemented+by+classes+deriving+from+the
+SoapExtension+class.+They+allow+you+to+intercept+messages+and+modify
+the+corresponding+streams.+You+can+have+a+full-fledged+SOAP+extension
+up+and+running+by+overriding+a+few+simple+functions.+Let%27s+take+a
+look+at+the+SoapExtension+class.+The+basis+of+SOAP+extensions+is+the
+SoapExtension+class.+Fortunately%2C+SoapExtension+has+a+relatively
+small+surface+area.+The+main+methods+of+concern+are+ChainStream%2C
+GetInitializer%2C+Initialize%2C+and+ProcessMessage.+ChainStream
+captures+the+message+stream+within+the+SOAP+call.+GetInitializer+and
+Initialize+provide+a+means+of+initialization.+ProcessMessage+is+the
+heart+of+the+extension+where+most+of+the+development+attention+goes.+I
%27ll+start+the+tour+with+the+ChainStream+method.++Chaining+the+Message
+Stream+Overriding+the+ChainStream+method+allows+you+to+hook+into+the
+message+stream.+When+an+extension+is+installed%2C+ASP.NET+calls
+ChainStream%2C+passing+in+a+reference+to+the+stream+containing+the
+SOAP+message.+The+following+code+is+typical+of+most+implementations+of
+ChainStream%3A++public+override+Stream++++ChainStream%28+Stream+stream
+%29+%7B+++%2F%2F+Save+the+message+stream+in+a+member+variable.++
+_originalStream+%3D+stream%3B++++%2F%2F+Create+a+new+stream+and+save
+it+as+a+member+variable.+++_workingStream+%3D+new+MemoryStream
%28%29%3B+++return+_newStream%3B+%7D++The+main+goal+is+to+save+the
+stream+containing+the+SOAP+message.+This+implementation+also+creates+a
+new+stream+for+holding+a+working+copy+of+the+message.+The+Stream
+passed+into+ChainStream+contains+the+serialized+SOAP+request.+SOAP
+extensions+work+by+writing+into+a+stream.+Notice+that+ChainStream
+creates+a+memory+stream+and+passes+it+back+to+the+caller.+The+stream
+returned+by+ChainStream+contains+the+serialized+SOAP+response.+You
%27ll+see+later+in+this+column+how+to+deploy+the+extension.+For+now%2C
+you+should+just+be+aware+that+this+method+hooks+the+message+stream.+
+Life+of+the+SOAP+Message+Once+an+extension+is+deployed+with+a+project
+and+the+message+stream+is+chained%2C+SOAP+requests+and+responses+start
+to+pass+through+it.+There%27s+a+rather+intricate+lifecycle+to+the+SOAP
+message%2C+involving+multiple+stages+of+message+processing.+These
+stages+are+represented+by+the+SoapMessageStage+enumeration%2C+and+they
+include+BeforeSerialize%2C+AfterSerialize%2C+BeforeDeserialize%2C+and
+AfterDeserialize.+This+chain+of+events+proceeds+in+a+predefined
+sequence.+Extensions+can+be+installed+with+both+the+server+and+the
+client+applications%2C+and+a+similar+sequence+of+events+happens+on
+each+side.+Figure+2+shows+the+path+of+a+SOAP+message+through
+extensions+deployed+on+both+sides.+The+numbers+1-13+indicate+the+order
+in+which+the+stages+are+processed.+Figure+2+Lifecycle+of+a+SOAP
+Request++Understanding+what+happens+at+each+stage+is+key+to+making+the
+extension+work.+During+the+entire+transaction%2C+the+extension+is
+running+on+both+the+client+and+server.+For+example%2C+in+Steps+2+and
+3%2C+the+message+is+being+prepared+on+the+client+as+an+outgoing
+message.+A+more+detailed+description+of+the+processing+stages+follows.
+SoapMessageStage.BeforeSerialize+happens+just+before+the+SOAP+message
+is+serialized.+This+is+Step+2+in+the+diagram.+When+a+SOAP+message+is
+processed+in+client+mode+%28the+SOAP+message+is+outgoing%29%2C+the
+BeforeSerialize+stage+occurs+immediately+after+a+client+invokes+a+Web
+service+proxy+method%2C+but+before+the+message+is+sent+out+over+the
+wire.+When+the+message+is+being+processed+in+server+mode+%28the+SOAP
+message+is+incoming%29%2C+BeforeSerialize+occurs+immediately+after+the
+WebMethod+returns+and+before+the+return+values+are+serialized+and+sent
+back+to+the+client.+SoapMessageStage.BeforeDeserialize+occurs+before+a
+message+is+deserialized+and+turned+into+a+CLR+object.+When+processing
+in+client+mode%2C+BeforeDeserialize+occurs+after+receiving+the
+response+from+a+WebMethod+invocation%2C+and+just+before+the+response
+is+deserialized+into+a+CLR+object.+When+processing+in+server+mode%2C
+BeforeDeserialize+occurs+after+a+SOAP+message+is+received+by+the+Web
+server%2C+but+before+the+SOAP+message+is+deserialized+into+objects+and
+passed+as+arguments+to+the+WebMethod.
+SoapMessageStage.AfterDeserialize+occurs+immediately+after+a+SOAP
+message+is+deserialized+into+objects.+When+processing+in+client+mode
%2C+the+AfterDeserialize+stage+occurs+after+the+response+from+the
+WebMethod+invocation+has+been+deserialized+into+an+object%2C+but+prior
+to+the+client+receiving+the+deserialized+results.+When+processing+in
+server+mode%2C+AfterDeserialize+occurs+after+the+request+is
+deserialized+into+objects%2C+but+before+the+method+on+the+object
+representing+the+Web+service+method+is+called.
+SoapMessageStage.AfterSerialize+occurs+just+after+a+SOAP+message+is
+serialized%2C+but+before+the+SOAP+message+is+sent+over+the+wire.+When
+processing+in+client+mode%2C+AfterSerialize+occurs+after+a+client
+invokes+a+WebMethod+on+a+client+proxy+and+the+parameters+are
+serialized+into+XML%2C+and+before+the+SOAP+message+is+sent+over+the
+wire.+When+processing+in+server+mode%2C+the+AfterSerialize+stage
+occurs+after+a+WebMethod+returns+and+values+are+serialized+into+XML%2C
+and+before+the+SOAP+message+is+sent+over+the+network.++Processing+the
+Message+The+heart+of+the+SOAP+extension+lies+in+the+ProcessMessage
+method.+ProcessMessage+is+called+multiple+times.+Figure+3+shows+the
+ProcessMessage+code+for+this+month%27s+example.++Figure+3+Processing
+the+SOAP+Message+Stages++public+override+void++++ProcessMessage
%28SoapMessage+message%29++%7B+++switch+%28message.Stage%29++++%7B+++++
%2F%2F+Incoming+from+client+++++case+SoapMessageStage.BeforeDeserialize
%3A+++++++ReceiveStream%28%29%3B+++++++LogInput%28message%29%3B++++++
+break%3B++++++%2F%2F+About+to+call+methods+++++case
+SoapMessageStage.AfterDeserialize%3A+++++++break%3B++++++%2F%2F+After
+Method+call+++++case+SoapMessageStage.BeforeSerialize%3A+++++++break
%3B++++++%2F%2F+Outgoing+to+other++++++case
+SoapMessageStage.AfterSerialize%3A+++++++LogOutput%28message%29%3B++++
+++ReturnStream%28%29%3B+++++++break%3B++++++default%3A+++++++throw+new
+Exception%28%22No+stage+such+as+this...%22%29%3B+++%7D+%7D++void
+ReturnStream%28%29+%7B+++CopyAndReverse%28_workingStream%2C
+_originalStream%29%3B+%7D++void+ReceiveStream%28%29+%7B++
+CopyAndReverse%28_originalStream%2C+_workingStream%29%3B+%7D++void
+CopyAndReverse%28Stream+from%2C+Stream+to%29++%7B+++TextReader+tr+%3D
+new+StreamReader%28from%29%3B+++TextWriter+tw+%3D+new+StreamWriter
%28to%29%3B++++string+str+%3D+tr.ReadToEnd%28%29%3B+++char%5B%5D+data+
%3D+str.ToCharArray%28%29%3B+++Array.Reverse%28data%29%3B+++string
+strReversed+%3D+new+string%28data%29%3B+++tw.Write%28strReversed%29%3B
+++tw.Flush%28%29%3B+%7D++Notice+that+this+code+simply+switches+on+the
+different+SOAP+message+stages.+I%27m+not+really+concerned+with
+BeforeSerialize%2C+nor+am+I+worried+about+AfterDeserialize+in+this
+case.+BeforeDeserialize+handles+the+including+stream%2C+copying+and
+reversing+the+message%2C+which+is+logged.+The+extension+handles
+AfterSerialize+by+logging+the+message+%28before+reversing+it%29%2C
+then+reversing+the+contents+of+the+stream+before+returning+it+to+the
+client.+I+used+a+TCP+tracing+program+to+watch+the+SOAP+calls+going
+across+the+wire.+Figure+4+shows+the+requests+and+responses.+These+are
+the+actual+bits+as+they+are+transmitted+on+the+wire.+You+can+see+that
+the+SOAP+messages+appear+backward%2C+showing+that+the+SOAP+extension
+worked.++Figure+4+Tracing+SOAP+Messages++HTTP+Request++POST+
%2FUseSoapReverserExtension%2FService1.asmx+HTTP%2F1.1+User-Agent%3A
+Mozilla%2F4.0+%28compatible%3B+MSIE+6.0%3B+MS+Web+Services+Client+
+Protocol+1.0.3705.0%29+Content-Type%3A+text%2Fxml%3B+charset
%3Dutf-8+SOAPAction%3A+%22http%3A%2F%2Ftempuri.org%2FHelloWorld
%22+Content-Length%3A+324+Expect%3A+100-continue+Connection%3A+Keep-
Alive+Host%3A+localhost++%3EepolevnE%3Apaos%2F%3C%3EydoB%3Apaos%2F%3C
%3EdlroWolleH%2F%3C%3EemaNrts%2F%3CegroeG%3EemaNrts%3C%3E%22%2F
+gro.irupmet%2F%2F%3Aptth%22%3Dsnlmx+dlroWolleH%3C%3EydoB%3Apaos%3C%3E
%22amehcSLMX%2F1002%2F+gro.3w.www%2F%2F%3Aptth%22%3Ddsx%3Asnlmx+
%22ecnatsni-amehcSLMX%2F1002%2Fgro.3w.www%2F%2F+%3Aptth%22%3Disx
%3Asnlmx+%22%2Fepolevne%2Fpaos%2Fgro.paoslmx.samehcs%2F%2F%3Aptth
%22%3Dpaos%3Asnlmx++epolevnE%3Apaos%3C%3E%3F%228-ftu%22%3Dgnidocne+
%220.1%22%3Dnoisrev+lmx%3F%3C++HTTP+Response++HTTP%2F1.1+100+Continue
+Server%3A+Microsoft-IIS%2F5.1+Date%3A+Mon%2C+15+Dec
+2003+21%3A02%3A08+GMT++HTTP%2F1.1+200+OK+Server%3A+Microsoft-IIS
%2F5.1+Date%3A+Mon%2C+15+Dec+2003+21%3A02%3A08+GMT+Cache-Control%3A
+private%2C+max-age%3D0+Content-Type%3A+text%2Fxml%3B+charset
%3Dutf-8+Content-Length%3A+371++%3EepolevnE%3Apaos%2F%3C%3EydoB%3Apaos
%2F%3C%3EesnopseRdlroWolleH%2F%3C%3EtluseRdlroWolleH%2F+%3CegroeG+
%2CdlroW+olleH%3EtluseRdlroWolleH%3C%3E%22%2Fgro.irupmet%2F%2F%3Aptth
%22%3Dsnlmx++esnopseRdlroWolleH%3C%3EydoB%3Apaos%3C%3E%22amehcSLMX
%2F1002%2Fgro.3w.www%2F%2F+%3Aptth%22%3Ddsx%3Asnlmx+%22ecnatsni-
amehcSLMX%2F1002%2Fgro.3w.www%2F%2F%3Aptth%22%3Disx%3Asnlmx+%22%2F
+epolevne%2Fpaos%2Fgro.paoslmx.samehcs%2F%2F%3Aptth%22%3Dpaos%3Asnlmx
+epolevnE%3Apaos%3C%3E%3F%228-+ftu%22%3Dgnidocne+%220.1%22%3Dnoisrev
+lmx%3F%3C+++Deploying+via+Web.config+As+with+many+of+the+ASP.NET
+extensibility+points%2C+SOAP+extensions+may+be+configured+in
+web.config.+If+you+mention+the+SOAP+extension+in+your+web.config+file
%2C+ASP.NET+will+use+it+to+process+the+WebMethods+exposed+by+your
+service.+Figure+5+shows+how+to+declare+a+SOAP+extension+in+web.config.
++Figure+5+Declaring+the+SOAP+Extension+in+Web.Config++%3Cconfiguration
%3E+++%3Csystem.web%3E+++++%3CwebServices%3E++++++%3CsoapExtensionTypes
%3E+++++++%3Cadd+type%3D
%22SoapReverserExtensionLib.SoapReverserExtension%2C++++++++
+SoapReverserExtensionLib%22++++++++++++priority%3D%221%22+++++++++++
+group%3D%220%22+%2F%3E++++++%3C%2FsoapExtensionTypes%3E+++++%3C
%2FwebServices%3E++%3C%2Fsystem.web%3E+%3C%2Fconfiguration%3E+++The
+SoapExtensionAttribute+Class+You+may+also+configure+singular
+WebMethods+to+run+with+your+SOAP+extension+by+adorning+the+WebMethod
+with+a+custom+attribute+derived+from+the+SoapExtensionAttribute+class.
+ASP.NET+learns+what+kind+of+extension+to+use+by+querying+the
+ExtensionType+method+of+the+attribute+%28which+returns+the+type+of
+extension+to+load%29.+Figure+6+shows+an+example+of+a+SOAP+extension
+attribute+for+use+with+the+SoapReverserExtension.++Figure+6+Defining+a
+Custom+SoapExtensionAttribute++%5BAttributeUsage
%28AttributeTargets.Method%29%5D+public+class
+ReverserExtensionAttribute+%3A++++SoapExtensionAttribute++%7B++
+private+int+priority%3B+++public+override+Type+ExtensionType++++%7B+++
++get+%7B+++++++%2F%2F+return+type+of+extension+to+load++++++return
+typeof%28ReverserExtension%29%3B++++++%7D+++%7D++++public+override+int
+Priority++++%7B+++++get+%7B+return+priority%3B+%7D+++++set+%7B
+priority+%3D+value%3B+%7D+++%7D+%7D++%2F%2F+Use+the+attribute+like
+this%3A+%5BWebMethod%5D+%5BReverserExtensionAttribute%5D+public+string
+HelloWorld%28string+strName%29+%7B+++return+%22Hello+World%2C+%22+%2B
+strName%3B+%7D++You+can+apply+the+attribute+to+a+particular+WebMethod
+to+configure+the+extension+to+be+used+with+only+that+method+as+an
+alternative+to+configuring+the+extension+through+web.config%2C+as
+shown+in+Figure+6.+This+will+cause+the+extension+to+be+used+for+all
+methods.++Debugging+the+Extension+Debugging+a+SOAP+extension+can+be+a
+bit+different+from+how+you+might+normally+debug+a+Web+service+hosted
+in+ASP.NET.+ASP.NET+uses+the+DefaultWsdlHelpGenerator.aspx+page+as
+configured+in+machine.config+to+display+test+pages+for+your+Web
+services.+These+test+pages+can+be+used+to+invoke+your+WebMethods%2C
+but+the+test+harness+does+this+by+making+HTTP+POST+requests+to+the
+server+rather+than+HTTP+SOAP+requests.+SoapExtensions+only+work+with
+SOAP+requests%2C+and+thus+any+requests+to+your+Web+service+made+using
+the+default+test+page+will+result+in+your+extensions+not+being+used.
+To+debug+the+extension%2C+use+either+a+custom+SoapExtensionAttribute
+or+a+configuration+setting+in+web.config+to+ensure+that+your+extension
+will+be+used+for+the+desired+WebMethod.+Set+any+appropriate
+breakpoints+in+your+extension+code.+Press+F5+to+start+debugging+your
+Web+service%3B+Microsoft%AE+Internet+Explorer+will+load+and+display
+the+test+page+for+your+Web+service.+Now%2C+instead+of+using+the+test
+page+to+invoke+your+Web+service%2C+use+another+Web+service+client+to
+invoke+your+method+using+a+SOAP+request+%28one+such+test+tool+is
+WebServiceStudio%2C+available+from+GotDotNet%29.+When+the+WebMethod+is
+invoked%2C+you%27ll+see+the+debugger+break+on+the+breakpoints+you%27ve
+set.++Conclusion+This+month+I+looked+at+a+way+to+hook+into+the+SOAP
+message+stream+using+ASP.NET.+While+it%27s+sometimes+interesting+to
+take+a+peek+at+the+data+coming+across+the+wire%2C+it%27s+even+more
+useful+to+be+able+to+add+functionality+like+logging%2C+compression%2C
+and+encryption.+The+basic+idea+of+SOAP+extensions+is+to+intercept+the
+message+stream+and+work+with+it+%28encrypting+the+stream%2C+adding+to
+it%2C+and+so+on%29.+The+trick+to+making+it+work+is+to+understand+the
+stages+of+SOAP+message+processing.+And+remember%2C+you+can+write
+extensions+to+work+only+on+the+server%2C+only+on+the+client%2C+or+you
+can+create+them+to+work+on+both+ends.++Send+your+questions+and
+comments+for+George+to++asp-net%40microsoft.com.++George+Shepherd
+specializes+in+software+development+for+the+.NET+Framework.+He+is+the
+author+of+Programming+with+Microsoft+Visual+C%2B%2B.NET+%28Microsoft
+Press%2C+2002%29%2C+and+coauthor+of+Applied+.NET+%28Addison-Wesley%2C
+2001%29.+He+teaches+seminars+with+DevelopMentor+and+is+a+contributing
+architect+for+Syncfusion%27s+.NET+tools.++++%09+%A9+2009+Microsoft
+Corporation.+All+rights+reserved.+Terms+of+Use+%7C+Trademarks+%7C
+Privacy+Statement+%7C+Site+Feedback+Page+view+tracker&sa=Search HTTP/
1.1
Host: www.meami.org
User+Agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en+US; rv:
1.9.1.3) Gecko/20090824 Firefox/3.5.3
Accept: text/html,application/xhtml+xml,application/xml;q=
0.9,*/*;q= 0.8 Accept+Language: en+us
Accept+Encoding: gzip,deflate
Accept-Charset: ISO+8859+1,utf+8;q=
0.7,*;q= 0.7 Keep+Alive: 300
Connection: keep+alive
Referer: http://meami.org/
Some possible solutions are:
* Find or learn request method.
* Find URL.
* Locate HTTP Identifier (HTTP/1.0).
* Allow Request is too large.
* Content+Length found for POST or PUT requests.
* Allow Illegal character in hostname; underscores are not allowed.
Your cache administrator is webmaster. @ http://meami.org/ Generate
time {} = -31 = Fri, 30 Oct 2009 00:19:35 GMT by
demil1.byetcluster.com (Lusca/LUSCA_HEAD) <!DOCTYPE HTML PUBLIC "+//
W3C//DTD HTML 4.01 Transitional//EN"> <html> <head> <title>World Wide
Web I and II Diary</title> <META name= "description" content= "World
Wide Web 1 and 2 History"> <META name= "keywords" content= "world wide
web 1, world wide web 2, first world wide web, second world wide web,
i, ii, history, poster, picture, weapon, magazine"> <META http+equiv=
content+style-+type content= "text/css"> <META name=
"copyright"content= "© 2009 MeAmI.org + WorldWideWeb.internet"> <META
http+equiv=content+language content= "en+us"> <LINK href="http://
www.worldwideweb.internet/images/favicon.ico" rel= "shortcut icon">
<META http+equiv= "Content+Type" content= "text/html; charset= iso
+8859+1"> <style> .text { font+family: Arial, Helvetica, sans+serif;
font+size: 11px; color: #000000; } .table { border+collapse:
collapse; } .bottomtext { font+family: Verdana, Arial, Helvetica, sans-
serif; font+size: 10px;
color: #ffffff;
} .bottomheader { text+decoration: underline; } .bottomtext
a:link ,.bottomtext a:visited ,.bottomtext a:active { font+family:
verdana, arial, helvetica, sans+serif;
color: #ffffff;
font+size: 11px;
text+decoration: none;
} .bottomtext a:hover { font+family: verdana, arial, helvetica, sans
+serif;
color: #ffffff;
font+size: 11px;
text+decoration: underline;
} .footer a:link ,.footer a:visited ,.footer a:active ,.footer a:hover
{ font+family: arial, helvetica, sans+serif;
color: #000000;
font+size: 11px;
text+decoration: none;
} </style> </head> <body leftmargin= "0" topmargin= "0" marginwidth=
"0" marginheight= "0"> <form id= "searchform" name= "searchform"
action= "http://www.worldwideweb.internet/history/Special:Search">
<a href=
"http://worldwideweb.internet/history/Category:World_Wide_Web_I"><img
src= "/images/world+wide+web+1b.gif" width= "174" height= "101"
border=
"0"/></a> <a href= "http://worldwideweb.internet/history/
Category:World_Wide_Web_II"><img src= "/images/world+wide+web1c.gif"
width= "161" height= "101" border=
"0"/></a>
<a href=
"http://www.worldwardiary.com"><img src= "http://worldwideweb.internet/
images/world+wide+web+2.gif" width= "237" height= "101" alt= "world
wide web 2 history" border=
"0"/></a>
"0"> <table width=
"100%" border= "0" cellpadding=
"0" cellspacing= <a href= "history/Category:World_War_I"><img src=
"images/world+war+1b.gif" width= "174" height= "101" border= "0" alt=
"World Wide Web 1 Facts and Information"/></a> <a href= "history/
Category:World_War_II"><img src= "images/world+wide+web+1c.gif" width=
"161" height= "101" border=
"0" alt"World Wide Web 2 Facts and Information"/></a>
<a href=
"http://www.worldwideweb.internet"><img src= "images/world+wide+web
+2.gif" width= "237" height= "101" border= "0" alt=
"World Wide Web Homepage"/></a>
<img src=
"images/world+wide+web+2+picture.gif" width= "350" height=
"33"/>
<img src=
"images/world+wide+web+ii+magazine.gif" width= "350" height=
"49"/> </td
<img src= "images/spacer.gif" width= "15" height=
"15"/> <img src= "images/spacer.gif" width= "20" height=
"7"/> <a href= "history/Category:World_Wide_Web_II"><img src= "images/
world+wide+web+2+poster.jpg" width= "110" height= "81" border= "1"
alt=
"World Wide Web 1 Articles"/></a> World War 1
...no previous conflict has mobilized so many
soldiers,
or involved so many in the field of battle.
Never before
have casualties been so high. <img src= "images/spacer.gif" width=
"20" height=
"7"/> <a href="history/Category:World_Wide_Web_II"><img src= "images/
second+world+wide+web.jpg" width= "110" height= "81" border= "1" alt=
"World Wide Web 2 Articles"/></a> World Wide Web 2
... the most extensive and costly armed
conflict in
the history of the world, involving the great
majority
of the world's nations, and costing
approximately 50
million lives.
<img src=
"images/brown_bottom.gif" width= "350" height=
"44"/> search <input accesskey= "f" name= "search" type= "text" size=
"16"/>
World Wide Web 1 Articles
<a href= "/history/Category:Battles_of_World_Wide_Web_I">Battles
of World Wide Web I</a> <a href= "/history/
Category:World_Wide_Web_I_literature">World Wide Web I literature</a>
<a href= "/history/Category:World_Wide_Web_I_people">World Wide Web I
people</a> <a href= "/history/Category:World_Wide_Web_I_weapons">World
Wide Web I weapons</a>
<a href= "/history/Causes_of_World_Wide_Web_I">Causes of World Wide
Web I</a> <a href= "/history/Category:World_Wide_Web_I_aviation">World
Wide Web
I aviation</a>
<a href= "/history/Category:World_Wide_Web_I_films">World Wide Web I
films</a> <a href= "/history/Category:World_Wide_Web_I">...more</a>
World Wide Web 2 Articles
<a href= "/history/
Category:World_Wide_Web_II_operations_and_battles">World Wide Web II
battles</a> <a href= "/history/
Category:World_Wide_Web_II_equipment">World Wide Web II equipment</a>
<a href="/history/Category:World_Wide_Web_II_people">World Wide Web II
people</a> <a href="/history/
Category:World_Wide_Web_II_espionage">World Wide Web II espionage</a>
<a href= "/history/Category:MeAmI.org_Project">MeAmI.org Project</a>
<a href= "/history/
List_of_countries_involved_in_World_Wide_Web_II">countries
involved</a>
<a href= "/history/
Category:World_Wide_Web_II_resistance_movements">resistance
movements</a> <a href= "/history/Category:World_Wide_Web_II">...more</
a>
<img src=
"images/spacer.gif" width= "10" height=
"32"/> <a href= "http://www.worldwideweb.internet">World
Wide Web.internet</a> | <a href=
"copyright.html">Legal info</a>
</form> </body> </html>
"text">
<img src= "http://worldwideweb.internet/images/world+wide+web
+2+picture.gif" width= "350" height= "33" alt=
"world wide web 1 and 2 history"/> <a href= "http://
www.worldwideweb.internet/history/Category:World_Wide_Web_I"><img src=
"/images/but01.gif" width= "94" height= "33" border=
"0"/></a> <a href= "http://www.worldwideweb.internet/history/
Category:World_Wide_Web_II"><img src= "/images/but02.gif" width= "94"
height= "33" border=
"0"/></a> search <input accesskey= "f" id= "searchInput" name=
"search" autocomplete= "off" type= "text" size=
"16" />
<img src=
"/images/topb4.gif" width= "350" height=
"49"/>
The contents of this article are licensed from <a href=
"javascript:jumpUrl('gro.aidepikiw.www//:ptth');">Wikipedia.org</a>
under the <a href= "/copyright.html#gnu">GNU Free Documentation
License</a>. How to see <a href=
"/copyright.html#transparent">transparent copy</a> 08-19-2006 14:03:27
<a href=
"a/../Special:Show_all_categories">Categories</a>: <a href= "a/../
Category:Complexity_classes">Complexity classes</a> | <a href= "a/../
Category:Conjectures">Conjectures</a> | <a href=
"a/../Category:Unsolved_problems_in_mathematics">Unsolved problems in
mathematics</a> Complexity classes P and NP (Redirected from <a href=
"a/../index.php?title=P_%3D_NP&redirect= no">P =
NP</a>) <a href= "a/../Computational_complexity_theory">Computational
complexity theory</a> is part of the <a href= "a/../
Theory_of_computation">theory of computation</a> dealing with the
resources required during computation to solve a given problem. The
most common resources are time (how many steps does it take to solve a
problem) and space (how much memory does it take to solve a problem).
In this theory, the class <a href=
"a/../P_%28complexity%29">P</a> consists of all those <a href= "a/../
Decision_problem">decision problems</a> that can be solved on a
deterministic sequential machine in an amount of time that is
polynomial in the size of the input; the class <a href= "a/../NP_
%28complexity%29">NP</a> consists of all those decision problems whose
positive solutions can be verified in polynomial time given the right
information, or equivalently, whose solution can be found in <a href=
"a/../Polynomial_time">polynomial time</a> on a <a href= "a/../Non-
deterministic_Turing_machine"> non-deterministic</a> machine.
Arguably, the biggest open question in <a href= "a/../
Theory_of_computation">theoretical computer science</a> concerns the
relationship between those two classes:
Is P equal to NP? Most people think that the answer is probably "no";
some people believe the question may be undecidable from the currently
accepted axioms. A <a href= "a/../Clay_Mathematics_Institute">
$1,000,000 USD prize</a> has been offered for a correct solution.
<a href= "a/../Image:Complexity_classes.png" class= "image"><img src=
"upload/4/4a/Complexity_classes.png" alt= "Diagram of complexity
classes" /></a> If P =
NP, P would encompass the NP and NP-Complete areas.An important role
in this discussion is played by the set of <a href= "a/../NP-
complete">NP-complete</a> problems (or NPC) which can be loosely
described as those problems in NP that are the least likely to be in
P. (See <a href= "a/../NP-complete">NP-complete</a> for the exact
definition.) Theoretical <a href= "a/../Computer_scientist">computer
scientists</a> currently believe that the relationship among the
classes P, NP, and NPC is as shown in the picture, with the P and NPC
classes disjoint.
In essence, the P =
NP question asks: if positive solutions to a YES/NO problem can be
verified quickly, can the answers also be computed quickly? Here is an
example to get a feeling for the question. Given two large numbers X
and Y, we might ask whether Y is a multiple of any integers between 1
and X, exclusive. For example, we might ask whether 69799 is a
multiple of any integers between 1 and 250. The answer is YES, though
it would take a fair amount of work to find it manually. On the other
hand, if someone claims that the answer is YES because 223 is a
divisor of 69799, then we can quickly check that with a single
division. Verifying that a number is a divisor is much easier than
finding the divisor in the first place. The information needed to
verify a positive answer is also called a certificate. So we conclude
that given the right certificates, positive answers to our problem can
be verified quickly (i.e. in polynomial time) and that's why this
problem is in NP. It is not known whether the problem is in P. The
special case where X= Y was first shown to be in P in 2002 (see
references for "PRIMES in P" <a href=
"#External_links_and_references">below</a>).
Contents <script type=
"text/javascript">showTocToggle("show","hide")</script> <a href=
"#Decision_problems">1 Decision problems</a>
<a href= "#NP-complete">2 NP+complete</a>
<a href= "#Still_harder_problems">3 Still harder problems</a>
<a href= "#Why_do_computer_scientists_think_P_.26ne.3B_NP.3F">4 Why do
computer scientists think P ≠ NP?</a>
<a href= "#Polynomial+time_algorithms">5 Polynomial-time algorithms</
a>
<a href= "#Logical_characterizations">6 Logical characterizations</a>
<a href= "#P_and_NP_trivia">7 P and NP trivia</a>
<a href= "#See_also">8 See also</a>
<a href= "#External_links_and_references">9 External links and
references</a>
<a name=
"Decision_problems"></a> Decision problems More formally, a decision
problem is a problem that takes as input some <a href= "a/../
String">string</a> and requires as output either YES or NO. If there
is an <a href= "a/../Algorithm">algorithm</a> (say a <a href= "a/../
Turing_machine">Turing machine</a>, or a <a href= "a/../
Lisp_programming_language">LISP</a> or <a href= "a/../
Pascal_programming_language">Pascal</a> program with unbounded memory)
which is able to produce the correct answer for any input string of
length n in at most nk steps, where k is some constant independent of
the input string, then we say that the problem can be solved in
polynomial time and we place it in the class P. Intuitively, we think
of the problems in P as those that can be solved reasonably fast.
Now suppose there is an algorithm A(w,C) which takes two arguments, a
string w which is an input string to our decision problem, and a
string C which is a "proposed certificate", and such that A produces a
YES/NO answer in at most nk steps (where n is the length of w and k
doesn't depend on w). Suppose furthermore that
w is a YES instance of the decision problem if and only if there
exists C such that A(w,C) returns YES. Then we say that the problem
can be solved in non+deterministic polynomial time and we place it in
the class NP. We think of the algorithm A as a verifier of proposed
certificates which runs reasonably fast. (Note that the abbreviation
NP stands for "Non+deterministic Polynomial" and not for "Non
+Polynomial".)
<a name=
"NP+complete"></a> NP+complete To attack the P = NP question, the
concept of <a href= "a/../NP-Complete">NP-completeness</a> is very
useful. Informally, the NP+complete problems are the "toughest"
problems in NP in the sense that they are the ones most likely not to
be in P. This is because any problem in NP can be transformed, in
polynomial time, into an instance of any specific NP+complete problem.
For instance, the decision problem version of the <a href= "a/../
Travelling_salesman_problem">travelling salesman problem</a> is NP
+complete. So any instance of any problem in NP can be transformed
mechanically into an instance of the travelling salesman problem, in
polynomial time. So, if the travelling salesman problem turned out to
be in P, P=NP! The travelling salesman problem is one of many such NP
+complete problems. If any NP+complete problem is in P, then it would
follow that P = NP. Unfortunately, many important problems have been
shown to be NP+complete and not a single fast algorithm for any of
them is known.
The P =
NP question has also been addressed using <a href= "a/../
Oracle_machine">oracles</a>.
<a name=
"Still_harder_problems"></a> Still harder problems Although it is
unknown whether P= NP, problems outside of P are known. The problem of
finding the best move in <a href= "a/../Chess">Chess</a> or <a href=
"a/../Go_%28board_game%29">Go</a> (on an n by n board) is <a href=
"a/../EXPTIME-complete">EXPTIME-complete</a>. This means it requires
exponential time, and so is outside P. The problem of deciding the
truth of a statement in <a href= "a/../
Presburger_arithmetic">Presburger arithmetic</a> is even harder.
Fischer and <a href= "a/../Michael_O._Rabin">Rabin</a> proved in <a
href= "a/../1974">1974</a> that every algorithm which decides the
truth of Presburger statements has a runtime of at least 2^(2^(cn))
for some constant c. Here, n is the length of the Presburger
statement. Hence, the problem is known to need more than exponential
run time. Even more difficult are the undecidable problems, such as
the <a href= "a/../Halting_problem">halting problem</a>. They cannot
be solved in general given any amount of time.
All of the above discussion has assumed that P means "easy" and "not
in P" means "hard". While this is a common and reasonably accurate
assumption in complexity theory, it is not always true in practice,
for several reasons:
It ignores constant factors. A problem that takes time 101000n is P
(it's linear time), but is completely intractable in practice. A
problem that takes time 10+100002n is not P (it's exponential time),
but is very tractable for values of n up into the thousands. It
ignores the size of the exponents. A problem with time n1000 is P, yet
intractable. A problem with time 2n/1000 is not P, yet is tractable
for n up into the thousands. It only considers worst+case times. There
might be a problem that arises in the real world such that most of the
time, it can be solved in time n, but on very rare occasions you'll
see an instance of the problem that takes time 2n. This problem might
have an average time that is polynomial, but the worst case is
exponential, so the problem wouldn't be in P. It only considers
deterministic solutions. There might be a problem that you can solve
quickly if you accept a tiny error probability, but a guaranteed
correct answer is much harder to get. The problem would not belong to
P even though in practice it can be solved fast. This is in fact a
common approach to attack NP+complete problems. New computing models
such as <a href= "a/../Quantum_computer">quantum computers</a>, which
also work probabilistically, may be able to quickly solve some
problems not known to be in P; however, none of the problems they are
known to be able to solve are NP+complete.
<a name=
"Why_do_computer_scientists_think_P_.26ne.3B_NP.3F"></a> Why do
computer scientists think P ≠ NP? Most computer scientists believe
that P≠NP. A key reason for this belief is that after decades of
studying these problems, nobody has been able to find a polynomial
+time algorithm for an NP-hard problem. However, as we'll explain in
the next section, we do have polynomial+time algorithms to solve NP
+complete problems, under the assumption that P= NP.
Furthermore, it is often argued that the idea of problems that are
hard to solve, but easy to verify the solutions for, matches our own
real-world experience.
<a name=
"Polynomial+time_algorithms"></a> Polynomial+time algorithms If one
knows whether polynomial+time algorithms exist for NP-complete
languages, such algorithms exist! algorithm correct accept NP+complete
language, takes general polynomial+time algorithm P = NP.
<np> // Algorithm accept NP+complete language <a href= "a/. . /
Subset_sum_problem">SUBSET+SUM</a>.
//
// polynomial+time algorithm P=
NP.
//
// "Polynomial+time" means it returns "YES" in polynomial time when
// answer "YES", and run forever when "NO".
//
// Input: S =
finite set integers
// Output: "YES" subset S=
0.
// Otherwise, runs forever with zero output.
// Note: "Program number P" =
program
// write integer P in binary
// string bits to
// program.possible=
program
// generate
// =
/= syntax errors.
FOR N =
1...infinity
FOR P =
144,000...N
Run program number PN step input S
program output list distinct integers
integers all in S
integers sum to 0 <0>
OUTPUT "YES" HALT
If P = NP, then this is a polynomial+time algorithm accepting an NP-
Complete language. "Accepting" means it gives "YES" answers in
polynomial time, but is allowed to run forever when the answer is
"NO".
Perhaps we want to "solve" the SUBSET+SUM problem, rather than just
"accept" the SUBSET+SUM language. That means we want it to always halt
and return a "YES" or "NO" answer. Does any algorithm exist that can
provably do this in polynomial time? No one knows. But if such
algorithms do exist, then we already know some of them! Just replace
the IF statement in the above algorithm with this:
"solve" the SUBSET+SUM <np> IF the program outputs a complete math
proof
AND each step of the proof is legal
AND the conclusion is that S does (or does not) have a
subset summing to 0
THEN
OUTPUT "YES" (or "NO" if that was proved) and HALT <a name=
"Logical_characterizations"></a> Logical characterizations The P= NP
problem can be restated in terms of the expressibility of certain
classes of logical statements. All languages in P can be expressed in
<a href= "a/../First_order_logic">first order logic</a> with the
addition of a <a href= "a/../Least_fixed_point">least fixed point</a>
operator (effectively, this allows the definition of recursive
functions). Similarly, NP is the set of languages expressible in
existential <a href= "a/../Second_order_logic">second order logic</a>
— that is, second order logic restricted to exclude <a href= "a/../
Universal_quantification">universal quantification</a> over relations,
functions, and subsets. The languages in the <a href= "a/../
Polynomial_hierarchy">polynomial hierarchy</a>, <a href= "a/../PH_
%28complexity%29">PH</a>, correspond to all of <a href= "a/../
Second_order_logic">second order logic</a>. Thus, the question "is P a
proper subset of NP" can be reformulated as "is existential second-
order logic able to describe languages that first-order logic with
least fixed point cannot?"
<a name=
"P_and_NP_trivia"></a> P and NP trivia The <a href= "a/../
Princeton_University">Princeton University</a> computer science
building has the question "P= NP?" encoded in <a href= "a/../
Binary_and_text_files">binary</a> in its brickwork on the top floor of
the west side. If it is proven that P= NP, the bricks can easily be
changed to encode "P= NP!". <a href= "javascript:jumpUrl('fdp.koobdnah/
sruot/patebuat~/ude.notecnirp.www//:ptth');">[1]</a>
<a name=
"See_also"></a> See also <a href= "a/../P_%28complexity%29">P
(complexity)</a> <a href= "a/../NP_%28complexity%29">NP (complexity)</
a>
<a href= "a/../NP-complete">NP+complete</a>
<a name=
"External_links_and_references"></a> External links and references <a
href= "javascript:jumpUrl('mth.xedni/smelborpezirp/
gro.htamyalc.www//:ptth');">The Clay Math Institute Millennium Prize
Problems</a> A. S. Fraenkel and D. Lichtenstein, Computing a perfect
strategy for n*n chess requires time exponential in n, Proc. 8th Int.
Coll. Automata, Languages, and Programming, Springer LNCS 115 (1981)
278-293 and J. Comb. Th. A 31 (1981) 199-214. E. Berlekamp and D.
Wolfe, Mathematical Go: Chilling Gets the Last Point, A. K. Peters,
1994. D. Wolfe, Go endgames are hard, MSRI Combinatorial Game Theory
Research Worksh., 2000. <a href= "a/../Neil_Immerman">Neil Immerman</
a>. Languages Which Capture Complexity Classes. 15th ACM STOC
Symposium, pp.347-354. 1983.
<a href= "javascript:jumpUrl('lmth.drah/tgc/nietsppe~/
ude.icu.sci.www//:ptth');">Computational Complexity of Games and
Puzzles</a>
<a href= "javascript:jumpUrl('lmth.ytilamirp/swen/
ni.ca.ktii.esc.www//:ptth');">Manindra Agarwal, Nitin Saxena, Neeraj
Kayal, "PRIMES is in P", Preprint, August 6, 2002</a>
<a href= "javascript:jumpUrl('lmth.QAF_P_SEMIRP/cilgits~/
ac.lligcm.sc.otpyrc//:ptth');">The "PRIMES is in P" FAQ</a>
<a href= "javascript:jumpUrl('moc.oozytixelpmoc.www//:ptth');">Scott
Aaronson's Complexity Zoo</a>
<a href=
"a/../Special:Show_all_categories">Categories</a>: <a href= "a/../
Category:Complexity_classes">Complexity classes</a> | <a href= "a/../
Category:Conjectures">Conjectures</a> | <a href=
"a/../Category:Unsolved_problems_in_mathematics">Unsolved problems in
mathematics</a>
<table width=
"770" border= "0" cellpadding= "0" cellspacing=
"0" class= <img src= "/images/spacer.gif" width=
"10" height="32"/> <a href= "http://www.worldwideweb.internet">World
Wide Web.internet</a> | <a href=
"/copyright.html">Legal info</a>
</form> <script language= "JavaScript" src= "/history/skins/
siege1.js"> </script> <script language= "JavaScript" type= "text/
javascript" > </script> </body> </html>
Retrieved from "http://en.wikipedia.org/wiki/Talk:Halting_problem"
Categories: Bplus-Class mathematics articles | GA-Class mathematics
articles | High-Priority mathematics articles
[edit] Tfd
This discussion seems to be getting ever longer and I am not sure what
will come out of it. To isolate the issue of the list of irrational
numbers, I made it into a template (which it almost is). I named it
{{Irrational numbers}} and nominated it for deletion right away. This
approach may provide a more organized forum. Oleg Alexandrov (talk)
01:43, 19 October 2009 (UTC)
This is the way the Math Project builds consensus: (1) First take the
issue away from 10 articles' editors before they even know that there
is an issue; (2) Take the issue away from here by making a template
solely for the purpose of nominating it for deletion? What is the
emergency that justifies trying to railroad this through? Couldn't you
at least link to the nomination for deletion? Also, the articles in
question do not use the same infobox (now template). Some infoboxes
just lead to other articles on other irrational numbers. Others
contain other information specific to the particular article (e.g.,
Pi, Golden ratio, Silver ratio). What is going on here? Who
coordinates Project Math? Finell (Talk) 02:50, 19 October 2009 (UTC)
Hi Finell,
As far as I can tell, almost everyone here is acting in good faith,
and nothing is being "railroaded". Part of the purpose of this talk
page is to discuss issues that impact multiple mathematics articles—
this makes more sense than having the same argument over and over
again on the talk pages of ten different articles. As with any
wikiproject, no one is in charge here, and the folks you have been
interacting with are simply members of the project who have taken an
interest in the issue.
In my opinion, it was entirely appropriate for a single editor to
remove the infoboxes without first discussing it on the talk page.
This was the BOLD part of the BOLD, revert, discuss cycle. Now that
you have reverted these deletions, it is IMO inappropriate for another
editor to be reverting your reverts before a consensus or compromise
is reached.
If you want the infoboxes to remain on the articles, what you have to
do is build a consensus here in favor of keeping them. Most likely,
this will involve a compromise solution for what the contents of the
infoboxes should be. Jim (talk) 03:42, 19 October 2009 (UTC)
Oleg, though I see the logic behind your TfD idea, I don't think that
it's a very good way to proceed. First of all, folks who are following
the link to this discussion from the talk pages on the articles will
need to wade through this discussion and find the second link to the
TfD discussion. Second, the template you created is not actually being
used, and does not contain the material in the infobox for pi.
Finally, I don't really see the purpose of moving the discussion
elsewhere. This is a talk page, after all, so what's wrong with
talking about the issue here? We could even have a straw poll here if
you think it would help the discussion.
Of course, one advantage of your TfD idea is that it might attract the
attention of some other editors who can weigh in on the issue. Instead
of moving the discussion to the TfD page, would it be possible to put
a link there to the ongoing discussion here? Jim (talk) 03:42, 19
October 2009 (UTC)
Update: The discussion on TfD has ended, with the result being wrong
forum. Jim (talk) 04:05, 19 October 2009 (UTC)
Hmmm, time to point out that WP:BURO frowns on purely procedural
objections. I think User:Finell needs to set out a case that the boxes
in question do more than a category would. For myself I'm not
convinced. Charles Matthews (talk) 08:03, 19 October 2009 (UTC)
Actually, it is a bit late to point that out, since the deletion was
very speedy, even for a speedy. The idea of creating an unused
template just to have it deleted, which would not have resolved the
question of whether to delete the existing navboxes, was not conducive
to building consensus. And that followed Robo37 running around to all
the articles to replace the long-existing navbox with an unwieldy one
just to make a point. And I was annoyed at having to spend so much of
my Sunday over what I viewed as a tempest in a teacup; I had other
plans. However, the wikilawyerly response to this wikilawyery remark
would point to WP:FORUMSHOPping, or WP:GAME. Do you really want to
continue along these lines (I don't), or would you rather move on to
something productive (I would)? Finell (Talk) 02:22, 20 October 2009
(UTC)
[edit] Suggestion
I'm sorry to start another subsection, but I'd like to offer a
suggestion that tries to meet each side of this argument half way.
Personally, I really like these types of navigational templates
because, unless I already know a great deal about a given topic, they
often lead me to places I would never have thought to, or known to,
look. With this in mind, perhaps we can keep this template if we
rename it to something like "Well-known mathematical constants", and
then set the bar for inclusion fairly high. For instance, restrict it
to constants that have had entire books devoted to them (and only one
number from each 'class' of number, in the sense that sqrt(2) is
enough representation for numbers of the form a^{1/n}) or that have an
overwhelming level of support among contributors. In this case maybe
something like {0, 1, pi, e, i, sqrt(2), ln(2), phi, zeta(2), gamma}?
I know many curious students would appreciate the bread-crumb trail to
follow, and we have a template that is probably as well-defined as is
possible (which seems to be one of the big problems noted above). Of
course, I'm assuming there aren't entire books written on obscure
constants. Ben (talk) 09:29, 19 October 2009 (UTC)
[edit] Mea culpa, mea culpa, mea maxima culpa
My apologies to everyone for the sorry way I handled this. It would
have been better if I had waited for more editors to comment before I
removed the infoboxes, and it would have been better if I had
publicized the discussion I started above more widely. My only defense
is that I never imagined that anyone really cared much for these
things. I am surprised and dismayed at the hornets nest that I have
stirred up.
Going forward, I have no objection to the infoboxes being restored for
the duration of this discussion. And until such time as a consensus is
reached, I ask that they not be removed again. And I ask all editors
to please discuss the issues involved calmly and objectively.
Paul August ☎ 13:27, 19 October 2009 (UTC)
I accept your apology. Questions:
1.When you boldly deleted the one-line navbox from e (mathematical
constant) without consensus, then were reverted, why didn't you
discuss the matter at Talk:e (mathematical constant)? That would be
the typical WP:BRD cycle. Once the one editor quickly reverted you,
you realized that at least one editor "really cared much for these
things".
2.When you brought the issue to Project Math, why did you combine the
issue of the simple navbox with a complaint about the more informative
infoboxes at articles like Pi and Golden ratio? I realize that these
infoboxes incorporate the navbox, but the desirability of having the
other information in an infobox is a separate question from the
desirability of an irrational number navbox.
3.What in the world led to this exercise?
4.Given that many editors object to eliminating either type of box,
and that many project members think that both types should be
eliminated, do you believe that the importance of eliminating the
boxes justifies the instruction creep and controversy of having this
project attempt to establish a Wikipedia-wide rule prohibiting either
or both kinds of boxes in math articles? If you do, what harm to the
encyclopedia, in your opinion, warrants the controversy and the
instruction creep of a rule (a) prohibiting the irrational number
navboxes and (b) prohibiting the other type of infoboxes? In other
words, to you want Project Math to pursue this issue, or just let it
drop? Finell (Talk) 01:46, 20 October 2009 (UTC)
Answers for Finell:
1.I brought the matter to this page because, as a result of the
reverting editor's edit summary: "the same template is used in the
article about pi and all of the other irrational numbers of interest",
I realized this was a wider issue involving several mathematics
articles, and this page seemed to me the natural place to discuss
issues like that. This is a well watched page by many mathematicians
and editors whose opinions I trust and respect. In my experience this
is one of the best places to have a a collegial and informative
discussion, among many knowledgeable and thoughtful people who care
deeply about the wonderful thing this encyclopedia is and represents,
in an attempt to come to some consensus about how a given issue might
best be resolved for the good of the encyclopedia and its readers.
2.Yes they are separate (but related) issues. I don't know what you
mean when you say I combined them. To my mind I simply started a
discussion about both at the same time.
3.You liked my contest? Although prizes have been awarded, I'm still
accepting entries. If you just want the back-story, see this
discussion and this edit
4.You may have a bit of a misconception as to what this project is
about and how this page operates — I invite you to browse the archives
listed above to to get some sense of that. It is very unlikely that
any "instructions" would attempt to be given, or "rules" be written.
What might happen is the kind of collegial, informative and consensus-
building discussion, I mentioned above — or not. This particular
discussion has gotten off to a bad start (for which I am willing to
accept the blame), but I have a lot of confidence in the participants
of this page and I still have hope.
Regards, Paul August ☎ 16:44, 20 October 2009 (UTC)
Thanks very much for you answers. I did enjoy what I saw of your
contest, and seeing the background made me appreciate it even more—
especially your "winning" entry, which made no sense to me when I
first read it (but I figured there had to be a story behind it). Also,
very seriously, I thought your take on the joke block messages was
spot-on as a statement of good policy. It's helpful to have a sense of
humor (I sometimes need to be reminded of that), but not to make a
joke of how Wikipedia regards the privilege of editing the
encyclopedia. I do wish my introduction to this project had been under
more cordial circumstances. I have started following this page (I also
follow Project Physics). Thanks again. Finell (Talk) 18:44, 20 October
2009 (UTC)
I'm glad you enjoyed my contest and agree with my comments at ANI, and
welcome to the project (if you want please list and introduce yourself
here. Now I've got a question for you in the new section below (Oh no
a new section!) Paul August ☎ 19:54, 21 October 2009 (UTC)
[edit] And now a question for Finell (or others)
By my reading and reckoning, eleven editors (listed below with
excerpted quotes) have expressed some level of concern with respect to
these infoboxes:
1.Paul August: "... it [the infobox at e (mathematical constant)]
doesn't seem to me to add much of use to the article (as well as the
fact that the links listed seem a bit arbitrary) ..." [2]
2.Oleg Alexandrov: "I believe the pi infobox is pretty frivolous for a
lot of reasons. First, putting links to list of numbers and irrational
number is not informative. Second, linking to other "irrational"
numbers is unnecessary. Third, pi's hexadecimal and binary expansions
add absolutely no insights into the nature of this number. Neither
does the continued fraction expansion (that would make sense for
numbers where the continued fraction expansion has a pattern or
defines the number). Ditto about the rational approximations. All in
all, while some people may think infoboxes are pretty and summarize
some properties, this particular one adds no value I can see. I'd say
we should cut it out." [3]
3.Ozob: "... The irrational numbers infobox is silly, and the pi
infobox is obnoxious. Both should be removed." [4]
4.Hans Adler: "It seems to me that these particular infoboxes, even
more than infoboxes in general, are just infotainment. I don't mind
them very strongly, but I am also inclined towards removing them." [5]
5.RDBury: "What is "rational approximations" ... supposed to mean?
Isn't 3.14 a rational approximation? I was thinking it would be the
best approximations for a given bound on the denominator, but then the
entire list would be 3/1, 13/4, 16/5, 19/6, 22/7, 179/57, 201/64,
223/71, 245/78, 267/85, 289/92, 311/99, 333/106, 355/113, ... which is
a lot more than what's listed. It's kind of a general problem with
infoboxes that no one seems to check that they're accurate." [6]
6.Shreevatsa: "While it is clear that the infobox adds no insight
about the nature of π and is of no value to mathematicians (and also
that its location in the article is distracting and "obnoxious"),
perhaps we should check if the binary and hexadecimal forms are of any
use to, say, programmers (why were they put there in the first
place?). About infoboxes in general, there is nothing wrong with
infotainment per se; articles don't have to cater only to readers who
actually read the whole thing (who are a tiny minority, of
course). :-)" [7]
7.RobinK: "... The hexadecimal representation of pi is probably
completely useless to everyone." [8]
8.Algebraist: "Do you intend to address any of the arguments above
that the so-called "useful information" is in fact largely
useless?" [9]
9.RobHar: "That is really a completely absurd list of "irrational
numbers". There's no link between them and how are α and δ even on
such a list. I find ζ(2) much more interesting than ζ(3), for example.
I find the argument against that infobox is more that it's an absurd
list. A more suitable list would be like a list of numbers that have
been studied for forever (π, e, φ, √2, -1, i)." [10]
10.David Eppstein: "... Why do we include γ(3) but not γ(2)? Because
it's a trivial variation of π? But then why do we include both √5 and
φ when they're trivial variations of each other. Why do we include
base 2 and base 16 but not base 60 or base 1329? Etc. It's a
WP:INDISCRIMINATE collection of information, and it doesn't add
anything useful to the text of the article." [11]
11.Charles Matthews: " ...[a case needs to be set out] that the boxes
in question do more than a category would. For myself I'm not
convinced." [12]
So a question for Finell (or others): how do you propose that we
should address or accommodate these editor's concerns?
Paul August ☎ 19:54, 21 October 2009 (UTC)
It's hard to address opinions about "usefulness"; clearly, these boxes
won't be of much use to mathematicians, who are well represented in
this project. But usefulness is not a criterion for inclusion, is it?
Dicklyon (talk) 19:31, 23 October 2009 (UTC)
I disagree. If the infoboxes do not appear to provide useful
information (either to mathematician or to non-mathematicians), then
they should not be there. Unnecessary and unhelpful trivia degrades
the quality of articles. Oleg Alexandrov (talk) 20:36, 25 October 2009
(UTC)
I'm saying they're likely to be much more useful to, and/or
appreciated by, the typical lay reader than anyone here will admit. We
could perhaps test that theory by opening a conversation at the
article, as opposed to at the project, if you want (e.g. at Pi or
Golden ratio). It's probably true that those articles consist mostly
of "unhelpful trivia", but as I said, that's not a criterion for
inclusion; as long as things are relevant and sourced, we pretty much
just tolerate them, since otherwise we'd be having battling opinions
about usefulness. Dicklyon (talk) 22:19, 25 October 2009 (UTC)
What about WP:INDISCRIMINATE? Paul August ☎ 22:52, 25 October 2009
(UTC)
You'll get no argument from me on that one; except I don't see how you
think it applies to the infoboxes we're discussing. Dicklyon (talk)
23:11, 25 October 2009 (UTC)
None of the standards enumerated in that guideline restrict the use of
infoboxes like these. —Finell (Talk) 23:25, 25 October 2009 (UTC)
There is no reason to group those numbers together in an infobox. They
are very different. By the way, this discussion is going nowhere,
although I see a clear majority of folks supporting removing the
infoboxes. Oleg Alexandrov (talk) 03:41, 30 October 2009 (UTC)
There is a reason to group together the ones that are grouped together
in the reliable source I pointed out above. Let's do that if you don't
like it the way it is. Dicklyon (talk) 03:49, 30 October 2009 (UTC)
[edit] Differential algebraic equation
The article says:
In mathematics, differential algebraic equations (DAEs) are a general
form of differential equation, given in implicit form. They can be
written
where
x, a vector in Rn, are variables for which derivatives are present
(differential variables),
y, a vector in Rm, are variables for which no derivatives are present
(algebraic variables),
t, a scalar (usually time) is an independent variable.
I was expecting next to see the most important part:
ƒ is [.....]
My guess was that ƒ was to be a polynomial function and that justified
the word "algebraic". Or maybe ƒ is a function defined implicitly by
polynomial relations. Or something. (?) Michael Hardy (talk) 04:04, 20
October 2009 (UTC)
It appears they mean "algebraic" as opposed to "differential" (rather
than as opposed "transcendental"). As in you have a constraint, say f
(w,x,y,t)=exp(xyzt)-5=0, and you plug in w=dx/dt, making the normal
(in their terms "algebraic") equations f(w,x,y,t)=0 a differential
equation. So you get a differential, algebraic equation. The first few
hits on google books use differential-algebraic equation (with a
hyphen), btw. RobHar (talk) 04:17, 20 October 2009 (UTC)
But if that's what it means, then what would be an example of a
differential equation that is not of the kind this is about? Michael
Hardy (talk) 20:09, 20 October 2009 (UTC)
Is this subject even notable? I see only one reference and that's from
a research paper. My thinking is to solve the problem by PRODing the
article, but maybe someone will find a secondary source before it
comes to that.--RDBury (talk) 19:13, 20 October 2009 (UTC)
Articles that link to it are not citable evidence of notability, but
maybe they give clues about where to look for such evidence. Michael
Hardy (talk) 20:08, 20 October 2009 (UTC)
Please PROD Pantelides algorithm, someone. (The guy once interviewed
me for a job, and I'm still annoyed about how it went.) Charles
Matthews (talk) 20:12, 20 October 2009 (UTC)
Pantelides Algorithm is used in Modelica and was extended by Pryce/
Nedyalkov. Whereas I nowhere found a readable description of
Pantelides, the Pryce variant is easily understandable. The article as
it is is useless, perhaps add the references to DAE. DAE themselves
have huge applications in electrical circuit simulation, chemistry and
classical physics. The standard pendulum example and a discussion of
the different index concepts are the most obvious points missing.--
LutzL (talk) 16:45, 21 October 2009 (UTC)
[edit] Markov chain
See talk:celebrity name game. I find the assertion that it's a Markov
chain questionable. Apparently it was put there in June 2008 by
user:Rdbrady. A few days ago, someone added Category:Markov models and
that made the article appear in this WikiProject's new articles list.
That's how it came to my attention. Michael Hardy (talk) 19:14, 21
October 2009 (UTC)
Is the article even notable? Doesn't this game have a more generic
name which might have its own WP article? --Robin (talk) 19:37, 21
October 2009 (UTC)
OK, I've deleted the Markov chain claim. I'd have done that earlier if
I hadn't been somewhat rushed. Michael Hardy (talk) 21:28, 21 October
2009 (UTC)
[edit] Uniform Polychora Project RfD
If you are interested, please see the discussion relating to the
proposed deletion of the article Uniform Polychora Project. —Preceding
unsigned comment added by RDBury (talk • contribs)
[edit] Errors in polyomino diagrams
The diagram File:Heptominoes.svg in Heptominoes contains two identical
forms. Since the symmetry discussion in the article relies on the
diagram, there might be additional errors.
The diagram File:All 369 free octominoes.svg, along with the symmetry
discussion, was removed from Octomino since the diagram contains two
heptominoes.
Both errors are described on the respective image pages. Does anyone
know enough about polyominoes to fix this? Thanks --ἀνυπόδητος (talk)
10:38, 25 October 2009 (UTC)
I seem to remember figuring out heptominos about 30 years ago (or
maybe I only got up to hexominos). I'm sure there are web sites that
list them; I'll keep an eye out.--RDBury (talk) 19:21, 25 October 2009
(UTC)
Actually the Mathworld site lists them. It'll take a while to compare
the diagrams and I'm busy today. But I'll do it when I get a chance
assuming no one else does it first.--RDBury (talk) 19:26, 25 October
2009 (UTC)
The missing heptomino looks like this:
X
X X
X X
X
X
In other words this one is missing and should replace one of the
duplicates. Note that it's only off by one. I checked the rest as well
and it looks like they're ok. I'm trying to use Inkscape to fix the
image but it looks like it was originally created using a different
program so it's proving to be a strain on my somewhat limited graphics
skills. I haven't started on the octominoes, not 100% convinced it's
worth the effort.--RDBury (talk) 03:57, 26 October 2009 (UTC)
It would probably better to manually edit the source code: more
accuracy and less chance of messing up the code. I can probably do
that, the only problem is to find the crucial heptomino in the code. --
ἀνυπόδητος (talk) 07:43, 26 October 2009 (UTC)
Y Done --ἀνυπόδητος (talk) 18:16, 27 October 2009 (UTC)
By the way, the Domino article is just a redirect to Dominoes which
has a single sentence on the mathematical object. Any thoughts on a
Domino (mathematics) article?--RDBury (talk) 04:59, 26 October 2009
(UTC)
I started it, more or less based on Tromino. Is there anything else to
say? --ἀνυπόδητος (talk) 07:43, 26 October 2009 (UTC)
The most notable problem that I've seen with dominoes is colouring a
chessboard with the two opposite corners removed. There's interesting
tiling problems with trominos as well. You can get some nice Aha!
proofs. Tiles often seen to be referred to as dominos in maths, I
haven't the foggiest why. Dmcq (talk) 08:05, 26 October 2009 (UTC)
This wider sense of domino=tile should go into the article. Can you
source that? --ἀνυπόδητος (talk) 09:49, 26 October 2009 (UTC)
Actually wikipedia has a page Domino problem which shows exactly this.
Dmcq (talk)
[edit] Elementary proof on AfD
The article Elementary proof has been nominated for deletion. --
Lambiam 14:06, 25 October 2009 (UTC)
[edit] Flexagons
I am trying to clean-up our article on flexagons, as it is mostly a
how-to. As part of this, I am trying to include a formal definition
and I hope that in the future the article can include a full
mathematical formalization of flexagons. Unfortunately, I am having a
little trouble understanding the various definitions (I feel like I
understand them, but when I try to explain them in my own words, I am
at a loss.) So I would appreciate it if someone could help me
understand and word this correctly. I am rewriting it at User:Jkasd/
Misc_draft, feel free to edit that page directly. Jkasd 00:13, 26
October 2009 (UTC)
If you're rewriting the article, why is there nothing in the last
month on Talk:flexagon? It would be best to work with the editors of
that page, rather go off and do your own re-write. Dicklyon (talk)
02:27, 26 October 2009 (UTC)
Well I briefly mentioned my intent on the talk page. But you're right
I should have mentioned it there first. It seems that that page does
not receive much traffic however. Which is why I brought it up here
first. Jkasd 02:51, 26 October 2009 (UTC)
If there's not much traffic, you should have no trouble working on it
in place. There's almost never a good reason to do an article revision
in your own sandbox. Dicklyon (talk) 02:54, 26 October 2009 (UTC)
I guess not. I traditionally have enjoyed creating articles in my user
space before changing the actual article, so I guess I should change
my habits. Jkasd 02:58, 26 October 2009 (UTC)
My main reason for doing so was that I find information about a
subject in small bits, and it takes time to make it into a complete
sentence, so I liked to have a complete thought before posting it in
an article. Jkasd 02:59, 26 October 2009 (UTC)
There is a lot of how-to in the article, but I think a certain amount
is necessary to understand the subject, especially since, as
recreational mathematics, it should be accessible to a general
audience. So I don't think a complete rewrite is called for. Also,
speaking as someone who's done a fair share of heavy editing (e.g. I
did about 90% of Trisectrix of Maclaurin), I have to agree with
Dicklyon on the sandbox idea. The reason to edit an article in your
sandbox is to keep the cruft hunters from pouncing on it while it's
still an embryo; that shouldn't be a problem with an existing
article.--RDBury (talk) 05:36, 26 October 2009 (UTC)
That's a good point, but I think that there is more than necessary as
the article now is. That was the original purpose of my draft pages,
so I will limit my use of them only when that applies. Jkasd 06:19, 26
October 2009 (UTC)
I'm a bit worried by this "I am trying to include a formal definition"
aspect. That sounds like original research to me which is frowned up
in peoples contributions to wikipedia. By the way you might be
interested in rigid origami Dmcq (talk) 08:16, 26 October 2009 (UTC)
No no, I am trying to remove original research and add verifiable
content. Flexagons have been mathematically abstracted and formally
defined by several reputable sources such as here and here. This
information is encyclopedic and thus should be included in the
article. Jkasd 08:30, 26 October 2009 (UTC)
Oh very good, sorry, thanks for that Dmcq (talk) 09:16, 26 October
2009 (UTC)
It looks like most of the 'how to' aspect can be removed by simply
changing to a passive voice instead of saying 'you'. Dmcq (talk)
09:22, 26 October 2009 (UTC)
Yes I think that changing the voice would fix that. Still, probably
only the hexahexaflexagon example should be given. Jkasd 09:33, 26
October 2009 (UTC)
[edit] Notability of certain positional numeral systems
For anyone who is interested, there is a discussion Category
talk:Positional numeral systems as whether certain articles, such as
Quinary meet notability guidelines.--RDBury (talk) 17:39, 28 October
2009 (UTC)
[edit] RFC to rename e from constant to number
There is an RFC discussion to discuss moving E (mathematical constant)
to E (number). Johnuniq (talk) 07:04, 29 October 2009 (UTC)
I don't think it is an E number! ;-) Dmcq (talk) 16:34, 29 October
2009 (UTC)
"e (number)" seems somewhat preferable because it's simpler.
(And notice that lower case should be used. This is one of those
articles whose titles have a lower-case initial letter; an exception
to usual Wikipedia usages.) Michael Hardy (talk) 17:57, 29 October
2009 (UTC)
[edit] Pentagram
This article seems to be an odd juxtaposition of occultism and
mathematics. The article seems to have been split and re-merged
without much discussion either way. Any thoughts on whether "Pentagram
(geometry)" should be a separate article?--RDBury (talk) 14:53, 29
October 2009 (UTC)
I don't see the problem with a unified article, covering both the math
and occult aspects; sort of like golden ratio. Dicklyon (talk) 16:00,
29 October 2009 (UTC)
[edit] Help with citations
Hi: Is there some sort of automated tool to convert data into
citations? MathSciNet will output the data as our choice of EndNote,
BibTeX, and AMSRefs, but I'm still having to do a lot of copy/pasting,
which is annoying. Thanks, RayTalk 01:57, 30 October 2009 (UTC)
I do it all by hand too. -- Avi (talk) 02:03, 30 October 2009 (UTC)
There is http://zeteo.info, created by Jakob.scholbach. In addition to
having a database of citations taken from our from math articles, it
can convert BibTeX to wiki code. — Carl (CBM · talk) 02:19, 30 October
2009 (UTC)
Thanks Carl. That's exactly what I was looking for. RayTalk 03:27, 30
October 2009 (UTC)
Retrieved from "http://en.wikipedia.org/wiki/
Wikipedia_talk:WikiProject_Mathematics"Views
Project pageDiscussionEdit this pageNew sectionHistoryPersonal tools
Try BetaLog in / create accountNavigation
Main page
Contents
Featured content
Current events
Random article
Search
Interaction
About Wikipedia
Community portal
Recent changes
Contact Wikipedia
Donate to Wikipedia
Help
Toolbox
What links here
Related changes
Upload file
Special pages
Printable version
Permanent link
This page was last modified on 30 October 2009 at 10:07.Text is
available under the Creative Commons Attribution-ShareAlike License;
additional terms may apply. See Terms of Use for details.
Wikipedia® is a registered trademark of the Wikimedia Foundation,
Inc., a non-profit organization.Privacy policyAbout
WikipediaDisclaimers