東華大學圖書館 |

語系: 繁體中文

說明(常見問題)

回圖書館首頁

手機版館藏查詢

登入

回首頁

切換: 標籤 | MARC模式 | ISBD

Asymptotic density and effective neg...

Astor, Eric P.

FindBook

Google Book

Amazon

博客來

Asymptotic density and effective negligibility.

紀錄類型:	書目-電子資源 : Monograph/item
正題名/作者:	Asymptotic density and effective negligibility./
作者:	Astor, Eric P.
面頁冊數:	77 p.
附註:	Source: Dissertation Abstracts International, Volume: 76-11(E), Section: B.
Contained By:	Dissertation Abstracts International76-11B(E).
標題:	Mathematics. -
電子資源:	http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3712049
ISBN:	9781321886085

Asymptotic density and effective negligibility.
Astor, Eric P.

Asymptotic density and effective negligibility. - 77 p.

Source: Dissertation Abstracts International, Volume: 76-11(E), Section: B.

Thesis (Ph.D.)--The University of Chicago, 2015.

In this thesis, we join the study of asymptotic computability, a project attempting to capture the idea that an algorithm might work correctly in all but a vanishing fraction of cases.

ISBN: 9781321886085Subjects--Topical Terms:

515831
Mathematics.

Asymptotic density and effective negligibility.
LDR:04238nmm a2200361 4500 001 2077517
005 20161114130322.5
008 170521s2015 ||||||||||||||||| ||eng d
020 $a 9781321886085
035 $a (MiAaPQ)AAI3712049
035 $a AAI3712049
040 $a MiAaPQ $c MiAaPQ
100 1 $a Astor, Eric P. $3 3193026
245 1 0 $a Asymptotic density and effective negligibility.
300 $a 77 p.
500 $a Source: Dissertation Abstracts International, Volume: 76-11(E), Section: B.
500 $a Advisers: Denis R. Hirschfeldt; Robert I. Soare.
502 $a Thesis (Ph.D.)--The University of Chicago, 2015.
520 $a In this thesis, we join the study of asymptotic computability, a project attempting to capture the idea that an algorithm might work correctly in all but a vanishing fraction of cases.
520 $a In collaboration with Hirschfeldt and Jockusch, broadening the original investigation of Jockusch and Schupp, we introduce dense computation, the weakest notion of asymptotic computability (requiring only that the correct answer is produced on a set of density 1), and effective dense computation, where every computation halts with either the correct answer or (on a set of density 0) a symbol denoting uncertainty. A few results make more precise the relationship between these notions and work already done with Jockusch and Schupp's original definitions of coarse and generic computability.
520 $a For all four types of asymptotic computation, including generic computation, we demonstrate that non-trivial upper cones have measure 0, building on recent work of Hirschfeldt, Jockusch, Kuyper, and Schupp in which they establish this for coarse computation. Their result transfers to yield a minimal pair for relative coarse computation; we generalize their method and extract a similar result for relative dense computation (and thus for its corresponding reducibility).
520 $a However, all of these notions of near-computation treat a set as negligible iff it has asymptotic density 0. Noting that this definition is not computably invariant, this produces some failures of intuition and a break with standard expectations in computability theory. For instance, as shown by Hamkins and Miasnikov, the halting problem is (in some formulations) effectively densely computable, even in polynomial time---yet this result appears fragile, as indicated by Rybalov.
520 $a In independent work, we respond to this by strengthening the approach of Jockusch and Schupp to avoid such phenomena; specifically, we introduce a new notion of intrinsic asymptotic density, invariant under computable permutation, with rich relations to both randomness and classical computability theory. For instance, we prove that the stochasticities corresponding to permutation randomness and injection randomness coincide, and identify said stochasticity as intrinsic density 1/2.
520 $a We then define sets of intrinsic density 0 to be effectively negligible, and classify this as a new immunity property, determining its position in the standard hierarchy from immune to cohesive for both general and Delta02 sets. We further characterize the Turing degrees of effectively negligible sets as those which are either high (a' ≥T 0") or compute a DNC (diagonally non-computable) function. In fact, this result holds over RCA0, demonstrating the reverse-mathematical equivalence of the principles ID0 and DOM &sext; DNR. .
520 $a Replacing Jockusch and Schupp's negligibility (density 0) by effective negligibility (intrinsic density 0), we then obtain new notions of intrinsically dense computation. Finally, we generalize Rice's Theorem to all forms of intrinsic dense computation, showing that no set that is 1-equivalent to a non-trivial index set is intrinsically densely computable; in particular, in contrast to ordinary dense computation, we see that the halting problem cannot be intrinsically densely computable.
590 $a School code: 0330.
650 4 $a Mathematics. $3 515831
650 4 $a Theoretical mathematics. $3 3173530
650 4 $a Computer science. $3 523869
690 $a 0405
690 $a 0642
690 $a 0984
710 2 $a The University of Chicago. $b Mathematics. $3 2049825
773 0 $t Dissertation Abstracts International $g 76-11B(E).
790 $a 0330
791 $a Ph.D.
792 $a 2015
793 $a English
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3712049