Skip to Main Content
 

Global Search Box

 
 
 
 

Files

File List


Masters Thesis.pdf (1.61 MB)

ETD Abstract Container

Abstract Header

Hypercomputing the Uncountable: Computing Over the Reals and Deciding the Mandelbrot Set with Infinite-Time Turing Machines

Causey, Colin J.
http://orcid.org/0000-0001-9088-357X
http://rave.ohiolink.edu/etdc/view?acc_num=case169385415891866

Abstract Details

2023, Master of Sciences, Case Western Reserve University, EECS - Computer and Information Sciences.
Hypercomputational theory studies models of computation that can compute beyond what is possible with Turing machines. One such model that has risen to prominence is the infinite-time Turing machine (ITTM), which generalizes the Turing machine by allowing the machine to compute for a transfinite ordinal length of time. In this thesis, we accomplish primarily three things. First, we rigorously demonstrate that a multi-core variant of the standard ITTM model is computationally equivalent to the standard model. In doing so, we develop an algorithm that allows an ITTM to simulate a multi-core ITTM and analyze the algorithm’s complexity. Second, we apply the ITTM model to computation over uncountable spaces, in particular the real and complex numbers. We develop and analyze infinite-time algorithms for addition, subtraction, multiplication, division, square root, complex modulus, and comparison, and we locate their complexity within the arithmetical and hyperarithmetical hierarchies. Third and finally, we apply these arithmetic algorithms to the development of an infinite-time decision algorithm for the Mandelbrot set. By analyzing this decision algorithm, we are able to prove multiple effective descriptive set theoretic properties of the Mandelbrot set.
Harold Connamacher (Committee Chair)
Colin McLarty (Committee Member)
Shuai Xu (Committee Member)
209 p.
Computer Science; Mathematics
hypercomputation; real computation; infinite-time Turing machines; theoretical computer science; algorithms; Mandelbrot set; transfinite ordinals

Recommended Citations

Citations

  • Causey, C. J. (2023). Hypercomputing the Uncountable: Computing Over the Reals and Deciding the Mandelbrot Set with Infinite-Time Turing Machines [Master's thesis, Case Western Reserve University]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=case169385415891866

    APA Style (7th edition)

  • Causey, Colin. Hypercomputing the Uncountable: Computing Over the Reals and Deciding the Mandelbrot Set with Infinite-Time Turing Machines. 2023. Case Western Reserve University, Master's thesis. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=case169385415891866.

    MLA Style (8th edition)

  • Causey, Colin. "Hypercomputing the Uncountable: Computing Over the Reals and Deciding the Mandelbrot Set with Infinite-Time Turing Machines." Master's thesis, Case Western Reserve University, 2023. http://rave.ohiolink.edu/etdc/view?acc_num=case169385415891866

    Chicago Manual of Style (17th edition)

case169385415891866
55
© 2023, all rights reserved.
This open access ETD is published by Case Western Reserve University School of Graduate Studies and OhioLINK.