Challenging variants of the Collatz Conjecture

Simple item page
dc.contributor.advisorAaronson, Scott
dc.contributor.advisorHeule, Marijn, 1979-
dc.creatorDenend, Matthew Alexander
dc.creator.orcid0000-0001-7002-7426
dc.date.accessioned2019-05-01T18:44:16Z
dc.date.available2019-05-01T18:44:16Z
dc.date.created2018-12
dc.date.issued2018-10-12
dc.date.submittedDecember 2018
dc.date.updated2019-05-01T18:44:16Z
dc.description.abstractThe Collatz Conjecture (also known as the 3N + 1 problem) is simple to explain, yet proving that all positive integers following the Collatz Mapping must converge to 1 has eluded mathematicians for over half a century. Aaronson and Heule are exploring solving the Collatz Conjecture using an approach involving string rewrite systems: Aaronson transformed the Conjecture into a string rewrite system and Heule has been applying parallel SAT solvers on instances of this system. Similar approaches have been applied successfully to other mathematical problems. We started looking into simpler variants of the conjecture. This thesis defines some of these variants and investigates easily provable as well as very hard variants. We study the hardness of unsolved variants by computing the number of rewrite steps needed up to 1 billion. Our hardness prediction method suggests that proving termination of the challenging variants should be considerably easier compared to solving the original conjecture.
dc.description.departmentComputer Science
dc.format.mimetypeapplication/pdf
dc.identifier.urihttps://hdl.handle.net/2152/74439
dc.identifier.urihttp://dx.doi.org/10.26153/tsw/1559
dc.language.isoen
dc.subjectCollatz Conjecture
dc.subject3X + 1 problem
dc.subjectString rewrite systems
dc.subjectSAT solving
dc.subjectMatrix interpretation
dc.titleChallenging variants of the Collatz Conjecture
dc.typeThesis
dc.type.materialtext
thesis.degree.departmentComputer Sciences
thesis.degree.disciplineComputer science
thesis.degree.grantorThe University of Texas at Austin
thesis.degree.levelMasters
thesis.degree.nameMaster of Science in Computer Science

Access full-text files

Original bundle

Now showing 1 - 1 of 1
Thumbnail Image
Name:
DENEND-THESIS-2018.pdf
Size:
567.09 KB
Format:
Adobe Portable Document Format
Download

License bundle

Now showing 1 - 2 of 2
No Thumbnail Available
Name:
PROQUEST_LICENSE.txt
Size:
4.45 KB
Format:
Plain Text
Description:
Download
No Thumbnail Available
Name:
LICENSE.txt
Size:
1.84 KB
Format:
Plain Text
Description:
Download

Collections

UT Electronic Theses and Dissertations