Talk:Algorithm characterizations: Difference between revisions

Revision as of 20:23, 19 March 2008

Latest revision as of 01:08, 24 January 2024

(30 intermediate revisions by 11 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 207 ⟶ 214:

== A paradoxical situation ==

This was a duplicate of the post at [[Talk:Algorithm#A_paradoxical_situation]]. To keep the discussion together, I have replaced it with that link. Please come to that page if you would like to discuss the matter. &mdash;&nbsp;Carl <small>([[User:CBM|CBM]]&nbsp;·&nbsp;[[User talk:CBM|talk]])</small> 20:44, 19 March 2008 (UTC)

Recently I have encountered a paradoxical situation. In the book of Lewis, H.R. and Papadimitriou, C.H. [1] on the page 246, the following Church-Turing thesis is formulated:

== Why I reverted a long Multipundit edit to "A problem of definition" ==

The change made by multipundit lengthened this section but added nothing that wasn't discussed in appropriate detail in appropriate sections further on. Multipundit made assertions without clarification, and added a bold assertion about a fringe topic, "inductive Turing machines", without much context or substantiation.

== can an algorithm produce infinite output? ==

The article [[recursively enumerable set]] says:

:* There is an algorithm that enumerates the members of S. That means that its output is simply a list of the members of S: s₁, s₂, s₃, ... . If necessary, this algorithm may run forever.

Is that a legitimate use of the "algorithm"? I can't find support for it in [[algorithm characterizations]]. I would say the set is recursively enumerable if there is an algorithm (recursive function) that takes input i and computes s_i. I think that a function that takes some finite or empty input and produces infinite output (a list of all the primes) but is computable for every initial segment of the output is called [[corecursive]]. I don't know if "algorithm" applies to that. [[Special:Contributions/66.127.52.47|66.127.52.47]] ([[User talk:66.127.52.47|talk]]) 21:19, 20 March 2010 (UTC)

:::This bleeding thing keeps coming up; we really should document things somewhere and be able to point to it. The fact is that there's an older sense of the word ''algorithm'' that requires it to halt in finite time on every input. However this restriction tends to get in the way more often than it clarifies, and I don't believe the word is very often used in this strict sense anymore. Of course "not very often" is not the same as "not" (and for that matter I'm not even all that sure about "not very often"), so one way or another we need to deal with the ambiguity wherever it comes up &mdash; we can't just silently pick one definition or the other, because that would confuse readers expecting the other definition. --[[User:Trovatore|Trovatore]] ([[User talk:Trovatore|talk]]) 21:31, 20 March 2010 (UTC)

::::Some of the algorithm characterizations in this article allow an algorithm to be partial recursive, i.e. on some inputs the algorithm might run forever while never producing any output. This question is different--whether an algorithm can run forever and produce an infinite amount of output. One can think of an algorithm as something that runs on a Turing machine, and a Turing machine as something that computes an abstract function but cannot do I/O. I/O can only happen through some external mechanism after the Turing machine enters a halt state. Some programming languages are organized around that concept, e.g. Haskell's I/O monad can be viewed that way. I agree that "algorithm" is still a reasonable common-sense term, but we ought to source such a usage, and we haven't yet done so as far as I can tell. [[Special:Contributions/66.127.52.47|66.127.52.47]] ([[User talk:66.127.52.47|talk]]) 21:53, 20 March 2010 (UTC)

::::::Um. Agree that it needs to be sourced. But a definition of ''algorithm'' that doesn't allow for I/O is seriously broken.

::::::The problem with referring to an algorithm as "something that runs on a Turing machine" is that it focuses too much attention on the details of TMs, which are beside the point. It's really ''programs'' that run on Turing machines, not algorithms. An algorithm is supposed to be a higher level of abstraction &mdash; you can change details of the program, without changing the algorithm it implements. --[[User:Trovatore|Trovatore]] ([[User talk:Trovatore|talk]]) 22:52, 20 March 2010 (UTC)

:It's just a figure of speech. Instead of saying "the algorithm can run forever" you could say "the algorithm takes ''n'' as input and returns, as output, ''s''_''n''". If the sequence depends on some other input ''k'', the algorithm takes both ''k'' and ''n'' as inputs. So there is not actually any individual computation of a natural number that runs forever; there is just a computable function that enumerates the sequence ''s''_''n'' as its range. All these English problems disappear as soon as one makes the slightest effort to replace "algorithm" with "computable function" as would usually be done in a recursion theory book. But the translation between "the algorithm takes no input, enumerates the sequence ''s''_''n'', and never halts" and "the algorithm takes ''n'' as input and returns ''s''_''n''" is so direct that using the first as a convenient way of expressing the second is extremely common and causes no problems in practice. If someone ever needs to prove something about such an "algorithm", the first step will simply be to choose a computable function whose range is the sequence ''s''_''n''.

:Similarly, the way that an algorithm has "input" during the course of its computation is simply to perform the computation relative to an oracle, and consult the oracle whenever it wants additional input. So talking about algorithms with input is simply a different way about talking about oracle computations. From the point of view of the algorithm, it makes no difference if the input is typed when it is asked (as one visualizes I/O) or is piped in from a pre-existing file (as with an oracle computation). &mdash;&nbsp;Carl <small>([[User:CBM|CBM]]&nbsp;·&nbsp;[[User talk:CBM|talk]])</small> 02:30, 21 March 2010 (UTC)

::The sentence in question is in the lead of [[recursively enumerable set]] and is intended to give the reader a feel for what RE means, not a precise definition. If the algorithm in question is represented by a partial recursive function, then that function could map 1 to ''s''₁, 2 to ''s''₂, etc.. Thus each (finite) part of the output is indexed by the input, and any particular execution of the ''algorithm'' only produces a finite output while the algorithm as a whole has an infinite output. [[User:JRSpriggs|JRSpriggs]] ([[User talk:JRSpriggs|talk]]) 07:02, 23 March 2010 (UTC)

== Removal of first sentence ==

[[User:Bhny|Bhny]] removed the first sentence, about ''algorithm'' not having a generally-accepted definition, as "uninformative and arguably wrong". While the sentence is problematic because it's unsourced, I don't see how it's either uninformative or arguably wrong.

It is definitely not wrong, because some insist that an algorithm must always terminate in a finite number of steps, and others do not. This is a very basic difference, and there is certainly no generally-accepted answer. It is informative to tell the reader that. --[[User:Trovatore|Trovatore]] ([[User talk:Trovatore|talk]]) 01:21, 18 August 2012 (UTC)

: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)

"''We therefore propose to adopt the Turing machine that halts on all inputs as the precise formal notion corresponding to the intuitive notion of an "[[algorithm]]."'' Nothing will be considered as an [[algorithm]] if it cannot be rendered as a Turing machine that is guaranteed to halt on all inputs, and all such machines will be rightfully called algorithms. This principle is known as the '''Church-Turing thesis'''."

--- Citation #2. This comes from the same talk page as the above, but further down; see #3:

As the conventional Turing machine does not in general satisfy this Church-Turing thesis, we come to a paradoxical statement:

:I just found a fantastic article at http://math.ucsd.edu/~sbuss/ResearchWeb/FutureOfLogic/paper.pdf (cited in a 2007 Dershowitz-Gurevich paper):

''Turing machine refutes Church-Turing thesis''.

::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

---

Indeed, a universal Turing machine cannot be "rendered as a Turing machine that is guaranteed to halt on all inputs."

Bill[[User:Wvbailey|Wvbailey]] ([[User talk:Wvbailey|talk]]) 01:52, 18 August 2012 (UTC)

By the way, if we take the original Turing machine described in the classical paper of Alan Turing (1936), as mentioned, we'll have more problems with the Church-Turing thesis.

== spelling, etc. ==

[1] Lewis, H.R. and Papadimitriou, C.H. Elements of the Theory of Computation, Prentice-Hall, Uppre Saddle River, N.J., 1998

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:

With respect to all discussion participants, [[User:Multipundit|Multipundit]] ([[User talk:Multipundit|talk]]) 20:23, 19 March 2008 (UTC)

: 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)