Talk:Blum axioms

This is the talk page for discussing improvements to the Blum axioms article.
This is not a forum for general discussion of the article's subject.

Put new text under old text. Click here to start a new topic.
New to Wikipedia? Welcome! Learn to edit; get help.

Article policies

Find sources: Google (books · news · scholar · free images · WP refs) · FENS · JSTOR · TWL

What is C(t) in the description of C⁰(f)? - 69.174.134.88 20:40, 12 June 2006 (UTC)[reply]

From the description below, it must be C(f).

C^{0}(f)\subseteq C(f)

holds, I just changed it. --GrGr 07:26, 14 June 2006 (UTC)[reply]

Definition: simple or formal?[edit]

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)[reply]

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)[reply]

Proposed Definition (Draft):

A Blum complexity measure is a function $\Phi$ mapping pairs $(M,x)$ to a natural number $\mathbb {N}$ or to infinity, where $M$ is a Turing Machine and $x$ is an input to $M$ . Furthermore, $\Phi$ should satify the following axioms:

$\Phi (M,x)$ is finite if and only if $M(x)$ halts
There is an algorithm which, on input $(M,x,n)$ decides if $\Phi (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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

Definition Phi:N->P(1) should be Phi:P(1)->N?[edit]

From the definition of Blum measure Phi:N->P⁽¹⁾ it appears that natural numbers are mapped onto P⁽¹⁾, while from the rest of the text it appears that it should be vice-versa: P⁽¹⁾ should be mapped onto natural numbers. Is this correct? Yuriy —The preceding unsigned comment was added by 128.177.16.7 (talk) 19:54, 23 February 2007 (UTC).[reply]

No. Phi_i is a partially computable function for each index i, so Phi is a map from indices to partially computable functions. 70.242.135.254 20:31, 4 September 2007 (UTC)[reply]

English description of what the axioms mean?[edit]

Is anyone willing to attempt an English description of the axioms? I can't quite see their significance from the mathspeak alone. --Doradus (talk) 04:54, 8 February 2008 (UTC)[reply]