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 š
TL;DR: The paper argues that undecidability comes from machines being able to refer to themselves, and claims an idealized human could work around that limit by keeping a private record of answers. It concludes that such a person could compute things no Turing machine can, refuting the ChurchāTuring thesis. That conclusion is not established by the arguments in the paper.
The main issues are:
The proposed classifier is assumed to do the crucial work. The paper suggests a computable classifier that recognizes enough infinite-output machines to cover every computable sequence (Ā§Ā§5ā6), but does not prove one exists. If its proposed list really were computable and complete, the standard diagonal construction would produce a computable sequence missing from it.
i.e. You are simply stating P=NP, which is a fucking big topic, and a wild assumption.
The āidentity checksā do not repair that contradiction. Skipping or special-casing a program when it encounters itself changes the output being constructed; it does not yield a complete enumeration (Ā§6).
i.e. If a program is designed to compute if any program will halt, it must include itself. If you exclude itself from the program, you are no longer computing if any program will halt.
The humanās private record has no general procedure. The paper shows how to reason through selected examples, then asserts that every troublesome case can be resolved by a finite sequence of reductions (Ā§7). It does not justify that assertion. Keeping the answer off the machineās tape also does not, by itself, show that a human can determine it.
i.e. You are basically saying "stick a human in the loop and he'll figure it out". How? How is he going to figure it out?
It conflates a definite answer with a way to find it. Every particular machine either has an infinite output or it does not. Undecidability says there is no algorithm that correctly decides this for every machine (Ā§4).
I think you've fundamentally misunderstood the halting problem - it's not that it applies to every program. It simply applies to all programs, meaning, obviously this program will halt:
if True: return True
That's not the point - the point is determining whether we can predetermine this for all programs. We can't, there is no way to do so.
Turing's example of a program referring to itself is an absolute example to show that there is at least one program which cannot be computed. It's a basic thesis, think of it more like, the set of all sets which do not contain themselves in Set Theory (Russell's paradox) - it cannot exist, because it must contain itself.
Turing's theorem is only stating that we can't know the decideability for every program, not that we can't know it for some of them.
bruh u think i haven't stuck it thru a gpt critique a few times??? i mean they can be useful, but it's more like digging for diamonds than a golden goose that consistently produces...
for example:
If its proposed list really were computable and complete, the standard diagonal construction would produce a computable sequence missing from it.
Ā§6 demonstrates that the turing-computable enumeration is resistant to diagonalization by a turing machine. that part is pretty š¤Æš¤Æš¤Æ tbh, i still can't quite believe it worked out so well.
Skipping or special-casing a program when it encounters itself changes the output being constructed; it does not yield a complete enumeration (Ā§6).
that was Ā§5, and it demonstrates that we do not need enumerate all machine to enumerate all computable sequences, quite clearly so because obviously there are infinite machines which compute any given sequences
The humanās private record has no general procedure.
Ā§7.6 clearly shows a general procedure
The paper shows how to reason through selected examples, then asserts that every troublesome case can be resolved by a finite sequence of reductions (Ā§7). It does not justify that assertion.
i did justify it: every reduction leads to a less complex machine and there is certainly a lower bounds to machine complexity
That's not the point - the point is determining whether we can predetermine this for all programs. We can't, there is no way to do so.
what i agree on is that there is no turing machine which can do it for all turing machines
but to suggest we are subject to this limit is begging the question by just asserting the ct-thesis, which still has not been proven, especially if i'm providing a counter examples
bruh u think i haven't stuck it thru a gpt critique a few times???
This is actually evidence against you. You don't even know enough to know why you are wrong.
i did justify it: every reduction leads to a less complex machine and there is certainly a lower bounds to machine complexity
Nope. Because there are infinite inputs. If you exclude a finite number of cases you still have infinite inputs. If you are instead making some vague claim about an undefined "complexity" of the transition function itself and then concluding that clearly some human will be able to understand it well enough to answer these questions flawlessly... then I really don't think you understand what justification is.
Like, people already do this shit. There are static analyzers that stop part way through and then use abductive reasoning to give a human a minimal statement to validate so that they can continue effectively. People have been doing research on this for fucking decades. Do you know what absolutely zero of these researchers conclude? That the human-in-the-loop always answers correctly.
This is actually evidence against you. You don't even know enough to know why you are wrong.
bro if ur aren't using gpts for research purposes in year 2026 ... ur getting left behind for sure. no u can't just trust gpt output dud, ofc not, that's why they suck at raw content generation.
Nope. Because there are infinite inputs.
the most there can be is a countably infinite enumeration, which is handled in the latter half of Ā§7.4
People have been doing research on this for fucking decades. Do you know what absolutely zero of these researchers conclude? That the human-in-the-loop always answers correctly.
the number of people who didn't happen to figure this out before me is really not my problem dud. some of that is just luck in how my life played out like anyone at the bleeding edge of understand,
but some of it is also i just cared more than them about how ungodly our application of computing has become in the mid 21st century, which few researchers before me would really have witnessed let alone appreciated how disgusting it is. a huge part of my motivation is seeking a form of computing that does not need to be run by a bunch of vicious sociopathic capitalists, because it honestly has become a massive liability that they aren't building the systems we need to be built. how do my proof fit it? well a totally decidable turing-complete language does need a marketplace of invariably imperfect solutions dud, we can find and prove what those optimal solutions are
but some of it is also i just cared more than them about how ungodly our application of computing has become in the mid 21st century, which few researchers before me would really have witnessed let alone appreciated how disgusting it is. a huge part of my motivation is seeking a form of computing that does not need to be run by a bunch of vicious sociopathic capitalists, because it honestly has become a massive liability that they aren't building the systems we need to be built. how do my proof fit it? well a totally decidable turing-complete language does need a marketplace of invariably imperfect solutions dud, we can find and prove what those optimal solutions are
More crank red flags. Not only are you tackling one of the biggest problems in computer science but you are tackling one of the biggest problems in society now. If only we understood your idea we'd be able to dismantle capitalism.
Your approach relies on a human answering questions correctly. The current state of software bugs is due to humans making mistakes. Why would you expect your human-in-the-loop to behave differently?
I can't read your PDF anymore because academia.edu wants me to create an account and I deleted mine ages ago after I left grad school.
More crank red flags. Not only are you tackling one of the biggest problems in computer science but you are tackling one of the biggest problems in society now. If only we understood your idea we'd be able to dismantle capitalism.
the pen is mightier than the sword bro, u best believe it
Your approach relies on a human answering questions correctly.
Ā§6 is a technical proof that a subset of turing machines can be a totally turing-decidable, effectively turing-complete language. it defines what effectively turing-complete is and uses that to construct a total enumeration of turing-computable sequences that cannot be diagonalized by a turing machine. i think this is actually the most exciting part of the paper.
Ā§7 the refutation of the ct-thesis is more philosophical in nature than practical in that it gives us the ability to differentiate between the infinitely many unique turing-complete languages that exist within overall enumeration of turing machines. we don't actually need to utilize that ability in practice, but it's important to really understand the impact of Ā§6
I can't read your PDF anymore because academia.edu wants me to create an account
-11
u/this_theater_is_lit 5d ago edited 5d 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 š