Content deleted Content added
→Removal of first sentence: Citation #1 |
m Maintain {{WPBS}} and vital articles: 1 WikiProject template. Create {{WPBS}}. Keep majority rating "B" in {{WPBS}}. Remove 1 same rating as {{WPBS}} in {{WikiProject Mathematics}}. Tag: |
||
| (13 intermediate revisions by 7 users not shown) | |||
Line 1:
{{WikiProject banner shell|class=B|
{{WikiProject Mathematics|priority=Low}}
}}
==Untitled==
There are several problems with unballanced quotes and unbalanced parantheses in the body of this article. I will try to fix this when I have access to a computer, but if there are any takers, feel free to preemt me.
It will take some work, however, yo make sure the integrity of quotes and citations. <!-- Template:Unsigned IP --><small class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/80.216.50.78|80.216.50.78]] ([[User talk:80.216.50.78#top|talk]]) 19:16, 21 March 2019 (UTC)</small> <!--Autosigned by SineBot-->
== Holding place -- Markov's (1954) definition of "algorithm" ==
Line 236 ⟶ 243:
:Algorithm already has a generally agreed definition here- [[algorithm]] [[User:Bhny|Bhny]] ([[User talk:Bhny|talk]]) 01:42, 18 August 2012 (UTC)
: "There is no generally-accepted definition of <subject>" is a really bad way to begin an article. There actually is a generally-accepted definition of algorithm, the problem is with a formal characterization of algorithm. Agreed? [[User:Bhny|Bhny]] ([[User talk:Bhny|talk]]) 01:58, 18 August 2012 (UTC)
No, not agreed. I provided two citations that also disagree. Gurevich actually asserts that an algorithm is a Turing machine, a mechanism, and not just a sequence of symbols that is interpretable by a target mechanism. Bill[[User:Wvbailey|Wvbailey]] ([[User talk:Wvbailey|talk]]) 15:00, 18 August 2012 (UTC)
---▼
There is no generally-accepted definition. The one at [[algorithm]] is definitely not generally accepted. It is perhaps ''widely'' accepted, but another widely-used meaning is something like "the semantic content of a program, after abstracting away implementation details", and does not require that the program terminate in finitely many steps. --[[User:Trovatore|Trovatore]] ([[User talk:Trovatore|talk]]) 20:03, 18 August 2012 (UTC)
Basically if you don't define the subject in the first sentence you don't have an article. The subject here is ''Algorithm characterizations'', so we need a definition of ''Algorithm characterizations''. [[User:Bhny|Bhny]] ([[User talk:Bhny|talk]]) 12:03, 19 August 2012 (UTC)
:The point of the article, or one of the points, is precisely that workers do ''not'' agree on the definition of "algorithm". You can't lose that. I am going to revert. --[[User:Trovatore|Trovatore]] ([[User talk:Trovatore|talk]]) 18:12, 19 August 2012 (UTC)
::I added a definition for the topic in front of that and cleaned it up a bit. Also we should probably say "researchers such as x and y are working on this" [[User:Bhny|Bhny]] ([[User talk:Bhny|talk]]) 22:40, 19 August 2012 (UTC)
== cItation #1 ==
Here's a citation. I cc'd this off the [[Unsolved problems in computer science]] talk page. Both it and its fellow Church-Turing thesis were deemed "unworthy":
Line 269 ⟶ 287:
Bill[[User:Wvbailey|Wvbailey]] ([[User talk:Wvbailey|talk]]) 01:45, 18 August 2012 (UTC)
--- Citation #2. This comes from the same talk page as the above, but further down; see #3:
:I just found a fantastic article at http://math.ucsd.edu/~sbuss/ResearchWeb/FutureOfLogic/paper.pdf (cited in a 2007 Dershowitz-Gurevich paper):
::Samual R. Buss, Alexander S. Kechris, Anand Pillay, and Richard A. Shore, “The Prospects for Mathematical Logic in the Twenty-first Century”.
:This paper came from a panel discussion of the Association for Symbolic logic held in Urbana-Champain, June 2000. In particular, under the heading “Computer Science” Shore stated the following three problems for computer science:
::”1. “Prove the Church-Turing thesis by finding intuitively obvious or at least clearly acceptable properties of computation that suffice to guarantee that any function so computed is recursive . . .. Perhaps the question is whether we can be sufficiently precise about what we mean by computation without reference to the method of carrying out the computation so as to give a more general or more convincing argument independent of the physical or logical implementation.
::”2. What does physics have to say about computability (and provability or logic)? Do physical restrictions on the one hand, or quantum computing on the other, mean that we should modify our understanding of computability or at least study other notions?
::”3. Find, and argue conclusively for, a formal definition of algorithm and the appropriate analog of the Church-Turing thesis. . ..Thus we want a definition that will up to some precise equivalence relation capture the notion that two algorithms are the same as opposed to just computing the same function.” (p. 7-8)
There is more from the other authors, including Sam Buss’s question about artificial intelligence, “logic for computer science”, etc. I highly recommend reading this article if someone is interested in expanding this wiki-article. wvbailey
▲---
Bill[[User:Wvbailey|Wvbailey]] ([[User talk:Wvbailey|talk]]) 01:52, 18 August 2012 (UTC)
== spelling, etc. ==
There were lots of instances in this article of Boolos-Burgess-Jeffrey instead of Boolos–Burgess–Jeffrey (i.e. a hyphen instead of an en-dash), and several of Church-Turing instead of Church–Turing, and some page ranges and parenthetical offsets with hyphens instead of en-dashes. I haven't fixed all of the latter yet. Note:
: pp. 5–30 (right)
: pp. 5-30 (wrong)
(This is codified in [[WP:MOS]].) [[Special:Contributions/174.53.163.119|174.53.163.119]] ([[User talk:174.53.163.119|talk]]) 15:20, 20 July 2013 (UTC)
| |||