Super-recursive algorithm - Revision history

Comp.arch at 22:15, 2 December 2024

2024-12-02T22:15:35Z

← Previous revision		Revision as of 22:15, 2 December 2024
Line 6:		Line 6:
	The term was introduced by Mark Burgin, whose book ''Super-recursive algorithms'' develops their theory and presents several mathematical models.		The term was introduced by Mark Burgin, whose book ''Super-recursive algorithms'' develops their theory and presents several mathematical models.

	Burgin argues that super-recursive algorithms can be used to disprove the [[~~Church-Turing~~ thesis]]. This point of view has been criticized within the mathematical community and is not widely accepted.		Burgin argues that super-recursive algorithms can be used to disprove the [[Church–Turing thesis]]. This point of view has been criticized within the mathematical community and is not widely accepted.

	== Definition ==		== Definition ==
Line 23:		Line 23:
	:"It is generally understood that for a computational result to be useful one must be able to at least recognize that it is indeed the result sought." (Davis 2006: 128)		:"It is generally understood that for a computational result to be useful one must be able to at least recognize that it is indeed the result sought." (Davis 2006: 128)

	==References==		== References ==

	* Burgin, Mark (2005), ''Super-recursive algorithms'', Monographs in computer science, Springer. {{isbn\|0-387-95569-0}}		* Burgin, Mark (2005), ''Super-recursive algorithms'', Monographs in computer science, Springer. {{isbn\|0-387-95569-0}}
Line 30:		Line 30:

	== External links ==		== External links ==
	* [~~http~~://www.la-acm.org/Archives/laacm9912.html A New Paradigm for Computation]. Los Angeles ACM Chapter Meeting, December 1, 1999.		* [https://www.la-acm.org/Archives/laacm9912.html A New Paradigm for Computation]. Los Angeles ACM Chapter Meeting, December 1, 1999.

	[[Category:Hypercomputation]]		[[Category:Hypercomputation]]

PrimeBOT: /* top */Task 44: clean up shortdesc whitespace issues

2024-04-06T17:21:29Z

top: Task 44: clean up shortdesc whitespace issues

← Previous revision		Revision as of 17:21, 6 April 2024
Line 1:		Line 1:
	{{short description\|Generalization of ordinary algorithms that compute more than Turing machines}}		{{short description\|Generalization of ordinary algorithms that compute more than Turing machines}}
	{{notability\|date=February 2024}}		{{notability\|date=February 2024}}
	{{No footnotes\|date=February 2023}}		{{No footnotes\|date=February 2023}}

David Gerard: /* References */

2024-02-11T15:21:19Z

References

← Previous revision		Revision as of 15:21, 11 February 2024
Line 27:		Line 27:
	* Burgin, Mark (2005), ''Super-recursive algorithms'', Monographs in computer science, Springer. {{isbn\|0-387-95569-0}}		* Burgin, Mark (2005), ''Super-recursive algorithms'', Monographs in computer science, Springer. {{isbn\|0-387-95569-0}}
	* Davis, Martin (2006), "[https://wayback.archive-it.org/all/20080221162316/http://people.cs.uchicago.edu/~simon/TEACH/28000/DavisUniversal.pdf The Church–Turing Thesis: Consensus and opposition]". Proceedings, Computability in Europe 2006. Lecture notes in computer science, 3988 pp. 125–132		* Davis, Martin (2006), "[https://wayback.archive-it.org/all/20080221162316/http://people.cs.uchicago.edu/~simon/TEACH/28000/DavisUniversal.pdf The Church–Turing Thesis: Consensus and opposition]". Proceedings, Computability in Europe 2006. Lecture notes in computer science, 3988 pp. 125–132
	* Peter Kugel, "It's time to think outside the computational box", ''Communications of the ACM'', Volume 48, Issue 11, November 2005		* Peter Kugel, [https://www.researchgate.net/publication/220425557_It%27s_time_to_think_outside_the_computational_box "It's time to think outside the computational box"], ''Communications of the ACM'', Volume 48, Issue 11, November 2005

	== External links ==		== External links ==

David Gerard: single subcat of the tree

2024-02-11T15:20:24Z

single subcat of the tree

← Previous revision		Revision as of 15:20, 11 February 2024
Line 32:		Line 32:
	* [http://www.la-acm.org/Archives/laacm9912.html A New Paradigm for Computation]. Los Angeles ACM Chapter Meeting, December 1, 1999.		* [http://www.la-acm.org/Archives/laacm9912.html A New Paradigm for Computation]. Los Angeles ACM Chapter Meeting, December 1, 1999.

	[[Category:Algorithms]]
	[[Category:Hypercomputation]]		[[Category:Hypercomputation]]
	[[Category:Theory of computation]]

David Gerard: this doesn't use the term at all

2024-02-11T15:16:23Z

this doesn't use the term at all

← Previous revision		Revision as of 15:16, 11 February 2024
Line 27:		Line 27:
	* Burgin, Mark (2005), ''Super-recursive algorithms'', Monographs in computer science, Springer. {{isbn\|0-387-95569-0}}		* Burgin, Mark (2005), ''Super-recursive algorithms'', Monographs in computer science, Springer. {{isbn\|0-387-95569-0}}
	* Davis, Martin (2006), "[https://wayback.archive-it.org/all/20080221162316/http://people.cs.uchicago.edu/~simon/TEACH/28000/DavisUniversal.pdf The Church–Turing Thesis: Consensus and opposition]". Proceedings, Computability in Europe 2006. Lecture notes in computer science, 3988 pp. 125–132		* Davis, Martin (2006), "[https://wayback.archive-it.org/all/20080221162316/http://people.cs.uchicago.edu/~simon/TEACH/28000/DavisUniversal.pdf The Church–Turing Thesis: Consensus and opposition]". Proceedings, Computability in Europe 2006. Lecture notes in computer science, 3988 pp. 125–132
	* Hagar, A. and Korolev, A. (2007) [http://philsci-archive.pitt.edu/archive/00003180/ "Quantum Hypercomputation – Hype or Computation?"]
	* Peter Kugel, "It's time to think outside the computational box", ''Communications of the ACM'', Volume 48, Issue 11, November 2005		* Peter Kugel, "It's time to think outside the computational box", ''Communications of the ACM'', Volume 48, Issue 11, November 2005

AnomieBOT: Dating maintenance tags: {{Notability}}

2024-02-10T17:40:19Z

Dating maintenance tags: {{Notability}}

← Previous revision		Revision as of 17:40, 10 February 2024
Line 1:		Line 1:
	{{short description\|Generalization of ordinary algorithms that compute more than Turing machines}}		{{short description\|Generalization of ordinary algorithms that compute more than Turing machines}}
	{{notability}}		{{notability\|date=February 2024}}
	{{No footnotes\|date=February 2023}}		{{No footnotes\|date=February 2023}}
	In [[computability theory]], '''super-recursive algorithms''' are posited as a generalization of [[hypercomputation]]: hypothetical [[algorithm]]s that are more powerful, that is, compute more than [[Turing machines]].		In [[computability theory]], '''super-recursive algorithms''' are posited as a generalization of [[hypercomputation]]: hypothetical [[algorithm]]s that are more powerful, that is, compute more than [[Turing machines]].

David Gerard: pretty sure this concept has no notability

2024-02-10T17:20:07Z

pretty sure this concept has no notability

← Previous revision		Revision as of 17:20, 10 February 2024
Line 1:		Line 1:
	{{short description\|Generalization of ordinary algorithms that compute more than Turing machines}}		{{short description\|Generalization of ordinary algorithms that compute more than Turing machines}}
			{{notability}}
	{{No footnotes\|date=February 2023}}		{{No footnotes\|date=February 2023}}
	In [[computability theory]], '''super-recursive algorithms''' are posited as a generalization of [[hypercomputation]]: hypothetical [[algorithm]]s that are more powerful, that is, compute more than [[Turing machines]].		In [[computability theory]], '''super-recursive algorithms''' are posited as a generalization of [[hypercomputation]]: hypothetical [[algorithm]]s that are more powerful, that is, compute more than [[Turing machines]].

David Gerard: rm another Burgin neologism

2024-02-10T17:19:20Z

rm another Burgin neologism

← Previous revision		Revision as of 17:19, 10 February 2024
Line 15:		Line 15:
	== Relation to the Church–Turing thesis ==		== Relation to the Church–Turing thesis ==

	The Church–Turing thesis in recursion theory relies on a particular definition of the term ''algorithm''. Based on definitions that are more general than the one commonly used in recursion theory, Burgin argues that super-recursive algorithms~~, such as '''inductive Turing machines'''~~ disprove the [[Church–Turing thesis]]. He furthermore claims to prove that super-recursive algorithms could hypothetically provide even greater efficiency gains than using [[quantum algorithms]].		The Church–Turing thesis in recursion theory relies on a particular definition of the term ''algorithm''. Based on his personal definitions that are more general than the one commonly used in recursion theory, Burgin argues that super-recursive algorithms disprove the [[Church–Turing thesis]]. He furthermore claims to prove that super-recursive algorithms could hypothetically provide even greater efficiency gains than using [[quantum algorithms]].

	Burgin's interpretation of super-recursive algorithms has encountered opposition in the mathematical community. One critic is logician [[Martin Davis (mathematician)\|Martin Davis]], who argues that Burgin's claims have been well understood "for decades". Davis states,		Burgin's interpretation of super-recursive algorithms has encountered opposition in the mathematical community. One critic is logician [[Martin Davis (mathematician)\|Martin Davis]], who argues that Burgin's claims have been well understood "for decades". Davis states,

David Gerard: all these links are dead or not reviews

2024-02-06T22:26:18Z

all these links are dead or not reviews

← Previous revision		Revision as of 22:26, 6 February 2024
Line 25:		Line 25:

	* Burgin, Mark (2005), ''Super-recursive algorithms'', Monographs in computer science, Springer. {{isbn\|0-387-95569-0}}		* Burgin, Mark (2005), ''Super-recursive algorithms'', Monographs in computer science, Springer. {{isbn\|0-387-95569-0}}
	**José Félix Costa, [http://www.ams.org/mathscinet/search/publdoc.html?pg1=IID&s1=193826&r=3&mx-pid=2246430 MR2246430 Review] in [[MathSciNet]].
	** Harvey Cohn (2005), [http://www.computingreviews.net/browse/browse_topics4.cfm?ccs_id=2376 CR131542 (0606-0574) Review] in [[Computing Reviews]]
	**Martin Davis (2007),[https://www.math.ucla.edu/~asl/bsl/1302/1302-004.ps Review] in ''[[Bulletin of Symbolic Logic]]'', v. 13 n. 2.
	** Marc L. Smith (2006), [http://comjnl.oxfordjournals.org/cgi/reprint/49/6/762-a.pdf Review] in ''[[The Computer Journal]]'', Vol. 49 No. 6
	**Review, Vilmar Trevisan (2005), [[Zentralblatt MATH]], Vol. 1070. Review [http://siba-sinmdb.unile.it/cgi-bin/zmen/ZMATH/en/quick.html?first=1&maxdocs=3&type=html&an=1070.68038&format=complete 1070.68038]
	* Davis, Martin (2006), "[https://wayback.archive-it.org/all/20080221162316/http://people.cs.uchicago.edu/~simon/TEACH/28000/DavisUniversal.pdf The Church–Turing Thesis: Consensus and opposition]". Proceedings, Computability in Europe 2006. Lecture notes in computer science, 3988 pp. 125–132		* Davis, Martin (2006), "[https://wayback.archive-it.org/all/20080221162316/http://people.cs.uchicago.edu/~simon/TEACH/28000/DavisUniversal.pdf The Church–Turing Thesis: Consensus and opposition]". Proceedings, Computability in Europe 2006. Lecture notes in computer science, 3988 pp. 125–132
	* Hagar, A. and Korolev, A. (2007) [http://philsci-archive.pitt.edu/archive/00003180/ "Quantum Hypercomputation – Hype or Computation?"]		* Hagar, A. and Korolev, A. (2007) [http://philsci-archive.pitt.edu/archive/00003180/ "Quantum Hypercomputation – Hype or Computation?"]

David Gerard: this isn't useful

2024-02-06T22:23:35Z

this isn't useful

← Previous revision		Revision as of 22:23, 6 February 2024
Line 11:		Line 11:
	Burgin (2005: 13) uses the term '''recursive algorithms''' for [[algorithm]]s that can be implemented on Turing machines, and uses the word ''algorithm'' in a more general sense. Then a '''super-recursive class of algorithms''' is "a class of algorithms in which it is possible to compute functions not computable by any [[Turing machine]]" (Burgin 2005: 107)		Burgin (2005: 13) uses the term '''recursive algorithms''' for [[algorithm]]s that can be implemented on Turing machines, and uses the word ''algorithm'' in a more general sense. Then a '''super-recursive class of algorithms''' is "a class of algorithms in which it is possible to compute functions not computable by any [[Turing machine]]" (Burgin 2005: 107)

	Super-recursive algorithms are also related to '''algorithmic schemes''', which are more general than super-recursive algorithms. Burgin argues (2005: 115) that it is necessary to make a clear distinction between super-recursive algorithms and those algorithmic schemes that are not algorithms. Under this distinction, some types of hypercomputation are obtained by super-recursive algorithms, e.g., inductive Turing machines, wile other types of hypercomputation are directed by algorithmic schemas, e.g., infinite time Turing machines. This explains how works on super-recursive algorithms are related to hypercomputation and vice versa. According to this argument, super-recursive algorithms are just one way of defining a hypercomputational process.		Super-recursive algorithms are also related to '''algorithmic schemes''', another novel concept from Burgin, which are more general than super-recursive algorithms. Burgin argues (2005: 115) that it is necessary to make a clear distinction between super-recursive algorithms and those algorithmic schemes that are not algorithms. Under this distinction, some types of hypercomputation are obtained by super-recursive algorithms.

	== Relation to the Church–Turing thesis ==		== Relation to the Church–Turing thesis ==

← Previous revision		Revision as of 17:21, 6 April 2024
Line 1:		Line 1:
	{{short description\|Generalization of ordinary algorithms that compute more than Turing machines}}		{{short description\|Generalization of ordinary algorithms that compute more than Turing machines}}
	{{notability\|date=February 2024}}		{{notability\|date=February 2024}}
	{{No footnotes\|date=February 2023}}		{{No footnotes\|date=February 2023}}