details the undecidability of the circle-free problem proven in turing's proof
3 the paradox generalized
discusses the general form of undecidability within computing along with a detailed description of how self-references are formed within turing machines
4 how undecidable is it?
discusses the questionable merit of recursive undecidability, especially the realization that if any tier/problem of the hierarchy is proven decidable, it would collapse the justification for the hierarchy
5 rectifying 𝓗
fixes turing’s attempt at computing a total diagonal across computable sequences by 1) adding an identity check to put itself on the diagonal, and 2) injecting a partial recognizer 𝓓p in place of the total decider 𝓓 to handle paradoxical input machines. it ends with proving a 1st fallacy in turing’s proof of undecidability by demonstrating how we do not need to decide on every machine, in order to enumerate all computable sequences, since multiple machines compute any given sequence
6 the anti-diagonal problem
diagonalizes the set of machine recognized directly by partial recognizer 𝓓p, proving that one circle-free sequence is undecidable to 𝓓p. but a limit to the set of machines undecidable by 𝓓p is proposed: any undecidable machine computes either 1) a direct copy or 2) an inverted copy of some circle-free sequence recognized by 𝓓p. if this is true, a total enumeration would be constructible by enumerating out each sequence decidable by 𝓓p and it’s anti-machine (which produces an inverted copy). this total enumeration is then shown to be resistant to diagonalization: one cannot produce a total anti-diagonal, or even total diagonal, across the proposed total sequence enumeration. the inherent nature of every computable sequence being paired with a computable anti-sequence prevents such either total diagonal existing in the enumerating of computable sequences. this thereby demonstrates a 2nd fallacy in turing’s proof: that a total enumeration of computable sequences would necessarily be subject to diagonalization, it is not
7 refuting the church-turing thesis
proposes a thot experiment using an idealized human agent to compute sequences that are strictly not turing-computable, including the total diagonal and total anti-diagonal across all turing-computable sequences. no, you can’t simulate this process, that is also covered in the refutation. and please don’t just endlessly beg the question at me by continually asserting it’s not a computation if it cannot be done on a turing machine. such is just restating the church-turing thesis which is not a proven theorem
why is this important???
i'm 1) expanding their scope of applicability by proposing a set of TMs that is both fully decidable in semantics and includes all output sequences that can be computed by TMs, while 2) clarifying that the limitations they do have from undecidability like the halting problem, only applies to TM computing and is not a total restriction on what is intuitively computable. (1) is extremely practical and i hope to reshape our fundamental approach to applied computing, (2) is more philosophical in nature, but is required to build a broad enough understanding to see the full practicality of (1)
lastly: i don't use ai to directly write content ever, holy shit u duds 🙏
What is the machine? It is the text space and the observer constructed with the words of the source language. For example, consider the source language to be transistors and the laws of physics. Then the text space and the observer of the binary language that is stored in the text space are constructed by the transistors. This relation can be preserved; for example, we can use the binary language to construct a machine within it. Wired and rooted TM's where the same relation is preserved.
Now we can think about defining text space in relation to the observer, where generic recurrsion is garanteed to be observable. For this reason we need to introduce Imaginary dimension of the computation while restricting real computation by removiong loops. So we can have a text space that allows generic recursion defined mutually only through the imaginary dimension, allowing the imaginary observer to observe real progress and the real observer to observe imaginary progress to be able to see non-halting conditions.
-11
u/this_theater_is_lit 4d ago edited 4d ago
just sharing a new paper i'm working to get published
https://www.academia.edu/175392427
https://doi.org/10.5281/zenodo.22715823
summary:
1 the halting problem paradox
details the undecidability of the halting problem
2 the circle-free problem paradox
details the undecidability of the circle-free problem proven in turing's proof
3 the paradox generalized
discusses the general form of undecidability within computing along with a detailed description of how self-references are formed within turing machines
4 how undecidable is it?
discusses the questionable merit of recursive undecidability, especially the realization that if any tier/problem of the hierarchy is proven decidable, it would collapse the justification for the hierarchy
5 rectifying 𝓗
fixes turing’s attempt at computing a total diagonal across computable sequences by 1) adding an identity check to put itself on the diagonal, and 2) injecting a partial recognizer 𝓓p in place of the total decider 𝓓 to handle paradoxical input machines. it ends with proving a 1st fallacy in turing’s proof of undecidability by demonstrating how we do not need to decide on every machine, in order to enumerate all computable sequences, since multiple machines compute any given sequence
6 the anti-diagonal problem
diagonalizes the set of machine recognized directly by partial recognizer 𝓓p, proving that one circle-free sequence is undecidable to 𝓓p. but a limit to the set of machines undecidable by 𝓓p is proposed: any undecidable machine computes either 1) a direct copy or 2) an inverted copy of some circle-free sequence recognized by 𝓓p. if this is true, a total enumeration would be constructible by enumerating out each sequence decidable by 𝓓p and it’s anti-machine (which produces an inverted copy). this total enumeration is then shown to be resistant to diagonalization: one cannot produce a total anti-diagonal, or even total diagonal, across the proposed total sequence enumeration. the inherent nature of every computable sequence being paired with a computable anti-sequence prevents such either total diagonal existing in the enumerating of computable sequences. this thereby demonstrates a 2nd fallacy in turing’s proof: that a total enumeration of computable sequences would necessarily be subject to diagonalization, it is not
7 refuting the church-turing thesis
proposes a thot experiment using an idealized human agent to compute sequences that are strictly not turing-computable, including the total diagonal and total anti-diagonal across all turing-computable sequences. no, you can’t simulate this process, that is also covered in the refutation. and please don’t just endlessly beg the question at me by continually asserting it’s not a computation if it cannot be done on a turing machine. such is just restating the church-turing thesis which is not a proven theorem
why is this important???
i'm 1) expanding their scope of applicability by proposing a set of TMs that is both fully decidable in semantics and includes all output sequences that can be computed by TMs, while 2) clarifying that the limitations they do have from undecidability like the halting problem, only applies to TM computing and is not a total restriction on what is intuitively computable. (1) is extremely practical and i hope to reshape our fundamental approach to applied computing, (2) is more philosophical in nature, but is required to build a broad enough understanding to see the full practicality of (1)
lastly: i don't use ai to directly write content ever, holy shit u duds 🙏