Talk:Blum axioms
From Wikipedia, the free encyclopedia
What is C(t) in the description of C0(f)? - 69.174.134.88 20:40, 12 June 2006 (UTC)
- From the description below, it must be C(f).
holds, I just changed it. --GrGr 07:26, 14 June 2006 (UTC)
[edit] Definition: simple or formal?
Hi all.I find the definition of the Blum axioms very difficult to understand in the way it is stated.What is Dom()? Sure I should know, shure I have known, and sure I could find out quickly. But check this definition (search for "Blum" in the page). Is'nt it clearer? Best regards --Powo 15:32, 8 December 2006 (UTC)
Hi all, Hi MathMartin. I think your changes to the previous definition made it clearer. However, imho it is still too formal. It is possible to define Blum measures in a simpler way. Slightly less formal, less general, but more intuitive. In other words, more appropriate for Wikipedia. I propose the follwoind draft of a definition, tell me what you think. --Powo 10:51, 10 December 2006 (UTC)
Proposed Definition (Draft):
A Blum complexity measure is a function Φ mapping pairs (M,x) to a natural number 
or to infinity, where M is a Turing Machine and x is an input to M. Furthermore, Φ should satify the following axioms:
- Φ(M,x) is finite if and only if M(x) halts
- There is an algorithm which, on input (M,x,n) decides if Φ(M,x) = n
Hmmm... I just browsed in the history of the page and I see my above proposed definition was actually the original one and it was decided to put a more formal definition. So i guess it is really a matter of taste. Maybe we can include both definitions? I DO think the current one is unecessarily obfuscated, this is wikipedia, not a Bourbaki formal math book! Think of that: the Blum axioms are very easy to understand (at least for a theoretical computer scientist), yeah? However, I had to struggle to understand the current definition, and I have a PhD in theoretical computer science!... Think of the average wikipedia user! That having been said, I will not argue to defend my POV. I'll let those more involved in the editing of this page make the decision and just use my above comments as a remark or suggestion. Have a nice day, --Powo 11:12, 10 December 2006 (UTC)
- Your version is easier to understand for someone who has studied Turing machines, but what is the point of an axiomatic complexity measures if you are tied to a non axiomatic computational model, the Turing machine ? I think the current focus of the article on computable functions instead of Turing machines is necessary. But in order to make the article accessible to more readers we should provide both definitions. MathMartin 12:42, 10 December 2006 (UTC)
-
- Fine. How shall we merge the "easy to understand" definition in the main article? We should add a bit of text to explain why we provide two definitions: one is "easyer to understand", while the other one is "more general"(?) Do you have any good idea on that? --Powo 12:46, 11 December 2006 (UTC)
I merged your version of the axioms into the Notes section (without logging in), which I often use to explain the definitions in an article in a less formal manner. Somewhere above you said:
- I'll let those more involved in the editing of this page make the decision and just use my above comments as a remark or suggestion.
At the moment there are only me and you involved in the editing of this page and I doubt there will be more people any time soon as this is a very specialized topic. ( As I am currently not interested in theoretical computer science articles its actually only you :) ). So if you do not like my version, be bold, and edit the article without any more discussion, but I hope you will keep the definition of the blum axioms in terms of computable functions. Cheers. MathMartin 17:45, 11 December 2006 (UTC)
- I just gave a look to your edits and they seem just fine. No need for further edits in my opinion. You've done a good job, bravo. Regards, --Powo 21:44, 13 December 2006 (UTC)
