Talk:Algorithm characterizations: Difference between revisions

Revision as of 01:42, 18 August 2012

Latest revision as of 01:08, 24 January 2024

(14 intermediate revisions by 7 users not shown)

Line 1:

{{WikiProject banner shell|class=B|

{{maths rating|class=B|priority=Low|field=foundations}}

{{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">—&nbsp;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":

. . .Algorithm: what is such a beast?. . .

This is a holding place for the following. The intent is not to push this or any other point of view, but to make the question evident. A number of epistomologic and mathematical issues bubble up from this:

: from https://research.microsoft.com/~gurevich/

:[164] Andreas Blass and Yuri Gurevich

:''"Algorithms: A Quest for Absolute Definitions"''

:Bulletin of the European Association for Theoretical Computer Science

:Number 81 (October 2003), pages 195-225.

:Reprinted in Chapter on Logic in Computer Science

:Current Trends in Theoretical Computer Science

:World Scientific, 2004, pages 283-311

:Reprinted in ''Church's Thesis After 70 Years''

:Ontos Verlag, 2006, 24-57

:See more details here

::What is an algorithm? The interest in this foundational problem is not only theoretical; applications include specification, validation and verification of software and hardware systems. We describe the quest to understand and define the notion of algorithm. We start with the Church-Turing thesis and contrast Church's and Turing's approaches, and we finish with some recent investigations.

:wvbailey[[User:Wvbailey|Wvbailey]] 00:48, 5 September 2007 (UTC)

Interesting. The problem could be stated as "when are two algorithms equivalent?". Seems worth adding, and less bogus than trying to prove the Church-Turing thesis. [[Special:Contributions/76.197.56.242|76.197.56.242]] ([[User talk:76.197.56.242|talk]]) 15:49, 11 August 2008 (UTC)

---

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)