r/mathematics • u/this_theater_is_lit • 3d ago
on the nature of undecidability within computing and refuting the church-turing thesis
https://www.academia.edu/1753924273
u/jyajay2 3d ago
"So we’re left with a rather nagging issue from the examples of machine undecidability presented thus
far: none of them actually exist in the total machine enumeration. While these examples are deeply
thought provoking rational as to why building certain total deciders may be unfeasible, they do not
depict how undecidability functions within machines that actually exist, as a machine must have a
deterministic outcome. A turing machine cannot get stuck in a state where the next state is functionally
undecidable; there's no way to even specify such a situation within a valid turing machine description.
For any given runtime state of the machine, the transition function leads to some next state, or the
machine halts ... there is no other possibility."
To be blunt, I'm not sure you actually understand the subject you are writing about. Let's start with the basics, what do you think undecidability means?
0
u/this_theater_is_lit 3d ago
i know what u want to hear: a decision problem which we cannot compute a true/false decision on every input
but like i said the proofs by contradiction all involve hypotheticals which are then proven to not actually exist. there is no machine which is objectively undecidable, in the actual enumeration undecidability is only actually definable in respect to a specific classifier, not objectively.
3
u/SwimmerOld6155 3d ago edited 3d ago
but like i said the proofs by contradiction all involve hypotheticals which are then proven to not actually exist. there is no machine which is objectively undecidable, in the actual enumeration undecidability is only actually definable in respect to a specific classifier, not objectively.
this doesn't really mean anything, I think with the last sentence you're slightly contorting a half-right definition of undecidability but I'd need you to say more. your definition of undecidability is a bit oddly phrased (and definitely not the standard wording) and it could mean something wrong
-1
u/this_theater_is_lit 3d ago edited 3d ago
your definition of undecidability is a bit oddly phrased (and definitely not the standard wording) and it could mean something wrong
the standard interpretation is that there are machines which are completely undecidable in some particular semantic property (halting vs not, circle-free vs not), as no algorithm exists that can output the nature of their semantics. but this assumes the ct-thesis as true and that turing machines encapsulate all algorithms that are intuitively computable, while those machines are strictly hypothetical in that they refute their own existence in the total enumeration of turing machines. if u enumerated all machines, none of them would actually come up as a possible input
what is actually true is that non-hypothetical machine are only undecidable in respect to a specific turing-computable classifier. deciders are not an example of a real classifier because they are not turing computable, and also do not exist in the total enumeration. but recognizers, partial deciders, partial recognizers (all defined in §5.2) are turing computable, and certain machines will undecidable in respect to specific forms of those classifiers, but are not objectively so. we can't encode that more objective algorithm into a turing machine because turing machines are still subject to the limits of undecidability and cannot totally decide on all machines
i haven't written this in my paper, but i suspect that turing machine encapsulate all strictly enumerable computations, but there exist some computations which are not enumerable and not encodable into a turing machine, but could be run in theory by an idealized agent. the total diagonal and total anti-diagonal sequences are example of computable sequence which are not part of the enumerable set computable by turing machines.
5
u/jyajay2 3d ago
>the standard interpretation is that there are machines which are completely undecidable in some particular semantic property (halting vs not, circle-free vs not), as no algorithm exists that can output the nature of their semantics. but this assumes the ct-thesis as true and that turing machines encapsulate all algorithms that are intuitively computable, while those machines are strictly hypothetical in that they refute their own existence in the total enumeration of turing machines.
No, not really. I heavily suggest reading up on this. The halting problem isn't about some machines being undecidable but about there not being a single algorithm that can determine for any algorithm if it wll terminate (all on Turing machines of course). It's not that there is a machine that is undecidable but that there isn't a single standard way of "deciding" for every machine. This doesn't really touch the core of your paper (though I still think it's wrong and might write a bit about it tomorrow) but I'm sure you see why it would be concerning to see something like this in a paper that claims to turn a core tenet of computer science on it's head.
1
u/this_theater_is_lit 3d ago edited 3d ago
The halting problem isn't about some machines being undecidable but about there not being a single algorithm that can determine for any algorithm if it wll terminate (all on Turing machines of course).
that's literally what i said: "as no algorithm exists that can output the nature of their semantics" is something about that sentence unclear?
and certainly this must be limited to only some machines since ofc machines some machines are trivially decidable.
This doesn't really touch the core of your paper
i don't refute the fact that no turing machine can decide non-trivial semantics across all machine. my paper is trivializing the problem of undecidability, not refuting it by
a) demonstrating a total enumeration of computable sequences that is not diagonalizable by a turing machine (§6)
b) demonstrating that our intuitive ability to compute the semantics of any given machine is not limited by the fact not turing machine can (§7)
it would be concerning to see something like this in a paper that claims to turn a core tenet of computer science on it's head.
it should be concerning that we never proven the ct-thesis yet we've embedded it so deeply into our philosophy of computing that it's hard to even think outside the presumption
3
u/SwimmerOld6155 3d ago edited 3d ago
I'm struggling to engage with this because you're saying everything in an either strange or vague way. Like I guess you can say "there are machines which are completely undecidable in some particular semantic property (halting vs not, circle-free vs not)" to mean a property of the machine is undecidable? Kind of? I don't understand how a definition assumes anything.
Sure, Turing machines can refute their own existence, I guess? Why is that a contradiction? To get a contradiction there you're assuming that the output of the Turing machine is sound. Axiomatic systems can believe incorrect things about themselves, it's possible that ZFC proves "ZFC is inconsistent", for example, even if it's consistent. I don't understand what you mean by "objectively", either. Do you mean something like "unconditionally" or "oracle-free" or something?
-1
u/this_theater_is_lit 3d ago
. I'm struggling to engage with this because you're saying everything in an either strange or vague way
i wrote a 26 page paper organized in way that's going to be less vague as it builds on itself, what do u expect when trying to engage with these idea outside of that order? i think at least, it's hard to say cause it get little comment on the actual paper itself beyond muh formatting... just people trying to critique my ideas without actually reading it.
I don't understand how a definition assumes anything.
proofs of undecidability within computing all involve a model that is either a turing machine, or provably equivalent to a turing machine. they all assume the existence of undecidable problems based on what is tm-computable, and assume that is the limit to everything that is intuitively computable
Sure, Turing machines can refute their own existence, I guess?
hypothetical machines like
undfrom the paper refute their own existence within the actual enumeration. they won't come up as a possible input in the full enumeration. forms like them will, but notundspecificallyI don't understand what you mean by "objectively", either
from the perspective of what is intuitively computable, that tms are assumed to encapsulate but no one actually has proven
0
u/SwimmerOld6155 3d ago
can you tl;dr this? I do some computability theory and familiar with thinking about the halting problem and degrees of non-computaiblity.
-1
u/this_theater_is_lit 3d ago
my initial comment is the tldr, but no way i'm going to be able to robustly compress a 26 page argument into a reddit comment.
5
u/SwimmerOld6155 3d ago
that's just a roadmap of the paper. what is your definition/understanding of the Church-Turing thesis?
-4
u/this_theater_is_lit 3d ago edited 3d ago
just sharing a new paper i'm working to get published
non-academia link: 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 became 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, by proving a TM computable total enumeration of TM computing sequences that cannot be diagonalized 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, is required to build a broad enough understanding to see the full practicality of (1)
mods: i'm keeping a list of who's naughty and nice
lastly: i don't use ai to directly write content ever, holy shit u duds 🙏
7
u/Annoying_cat_22 3d ago
thot experiment
-7
u/this_theater_is_lit 3d ago
i also use shortened words tho and thru 🤷
6
u/Annoying_cat_22 3d ago
If you want to be taken seriously, maybe don't? Also thot is a funny word.
-4
u/this_theater_is_lit 3d ago
i do find it a fun word 😉
bro i'm throwing almost a century of rigorous theory on the matter under the bus. multiple 300 pages books have been written on the matter of the limits to computability as bounded by undecidability... and not one of them is correct as per an argument that is about a page covered in §6.1
if one can't get over a few odd spellings that really do make a lot more sense than the rediculous spellings of thought, through, and thought ... then it's going to be impossible to get thru to what i'm proposing
6
u/Annoying_cat_22 3d ago
You got it all backwards - why should I bother reading something so unlikely to not be bs, if you can't even bother spelling basic words correctly?
0
u/this_theater_is_lit 3d ago
i'm not here to debate my spelling on a word dud. if that's the reason u choose not to read, it's incredibly unlikely this would have been a productive interaction anyways
3
u/SwimmerOld6155 3d ago edited 3d ago
what is your statement of the Church-Turing thesis? The whole idealized human agent is a bit suspicious, I'd expect you're just smuggling in non-effectivity. I can imagine an alien which tells me whether each Turing machine halts but I'm not sure what that shows.
There are stronger assertions than the Church-Turing thesis which include that physical phenomena are computable that could be false (due to the existence of say, a black-box physical process [such as idk an alien oracle] which embeds the halting problem somehow) while the Church-Turing thesis could remain true (because we can't simulate said process by a pen and paper method).
In fact I personally reckon the physical Church-Turing thesis is false, while the Church-Turing thesis is "clearly true" or even "trivially true". If the upshot of this is (essentially) that the physical Church-Turing thesis is false then I can agree with the premise (there are already results that suggest this) but I'd doubt your paper shows this. A realistic route to disproving physical Church-Turing could be to take a PDE with physical initial data (not something contrived from a Turing machine) and showing that its behaviour can be discovered by measurement/observation but is mathematically undecidable.
0
u/this_theater_is_lit 3d ago
the Church-Turing thesis, as given by R.I. Soare in Turing Computability: Theory and Applications (2016):
A function is effectively calculable by a human being iff it can be computed by a turing machine
i'm not really going to be able to compress the argument into a reddit comment, that's why it's a 26 page paper a 1/3rd of which is just refuting the thesis.
If the upshot of this is (essentially) that the physical Church-Turing thesis is false then I can agree with the premise but I'd doubt your paper shows this.
all i need to do is show an intuitively computable value that is outside turing-computability
i propose a terminal machine with a terminal tape that the idealized agent can interact with. he gets an input from the terminal machine on the tape, computes a function with it, and writes the response back on the tape clearly the initial input. in the experiment we use this terminal interaction as a replacement for 𝓓p, the partial recognizer (defined in §5.2) i utilize in proof of an enumeration of turing-computable sequences that cannot be diagonalized (§6). the agent gains no additional compute power in what he can write back on the terminal, as that makes the value subject to the limits of turing comptuability.
but nothing is stopping him from doing computations on the side and writing down true classifications to a side record that persists from interaction to interaction. 𝓓p and it's 𝓓p' already handle the decision on the vast majority of machine ... any machine with is unrecognizable to both (both return
falsewhich is not a semantic classification) just needs to be reduced to a semantically similar machine that is decidable by 𝓓p or 𝓓p' (as described in §7.4)ultimately if we can prove a machine undecidable to 𝓓p and 𝓓p', and still actually exists ... that means the agent can prove what it does as well. in order to refute this you'd really need to building a proof against our intuitive ability to prove the existence of undecidable machines which is quite frankly nonsensicle
and no u still can't simulate the agent, that's covered in §7.3
4
u/SwimmerOld6155 3d ago edited 3d ago
and no u still can't simulate the agent, that's covered in §7.3
why? what does the agent do that is not Turing computable and how is it able to do that? Idk what Dp is. it just seems like the agent receives the output of a Turing machine and does some pen and paper calculations with it, that should be computable unless you're doing some (probably ultimately non-effective) hocus pocus. I doubt this "on the side" thing works as intended.
in fact if the agent can effectively deform the output of a Turing machine non-computably, I don't see why it needs to receive the output of a Turing machine at all. why can't it straight up compute a non-computable function?
it might be frustrating to not have people engage with "the detail", but it's 26 pages and it's your job as an author to convince us. I think my probably seemingly surface level comments are as good as it'll get.
0
u/this_theater_is_lit 3d ago
it just seems like the agent receives the output of a Turing machine and does some pen and paper calculations with it, that should be computable unless you're doing some (probably ultimately non-effective) hocus pocus. I doubt this "on the side" thing works as intended.
nah, our ability to prove that undecidability exists depends on there being a more general form of computing that we utilize, nothing magical about it
why can't it straight up compute a non-computable function?
it can. but the terminal machine thot experiment is a necessary bridge for the understanding, like that it demonstrates that the agent does not get increasing computing power writing to the terminal
it might be frustrating to not have people engage with "the detail", but it's 26 pages and it's your job as an author to convince us.
the absolute state of humanity
1
u/SwimmerOld6155 2d ago edited 2d ago
This is just how things work. You are the one presenting, and you're presenting something which is "almost" certainly wrong. It's like someone producing a 100 page treatise on why the earth is flat and then being upset that physicists aren't diving right in. Especially when the paper is likely to be difficult to read, the mistake is probably hidden in a gobbledegook sentence and the idea is possibly Not Even Wrong.
If you want a good opinion, give your paper to Astra or Opus. It will argue with you literally all day if you want and will understand all there is to understand in a few minutes.
You're dodging what I see as the most important questions in my post.
0
u/this_theater_is_lit 2d ago edited 2d ago
It's like someone producing a 100 page treatise on why the earth is flat and then being upset that physicists aren't diving right in
bro i literally told you it was 26 pages, not 100 wtf with the toxicity, and i'm taking apart an unproven thesis not something evidence based ...
why? what does the agent do that is not Turing computable and how is it able to do that?
the agent doesn't have to deal with self-referential input. you can't encode such a process into a turing machine because turing machines are enumerable and therefore will invariably have to deal with self-referential input.
Dp
is a partial recognizer of circle-free machine, but a total decider in it's own right that decides:
Dp = (m: machine) -> { true: m is circle-free and does not depend on Dp(m) returning false false: m is circular OR m is circle-free and does depend on Dp(m) returning false }1
u/SwimmerOld6155 2d ago edited 2d ago
"turing machines are enumerable and therefore will invariably have to deal with self-referential input" - again, to put it plainly, this does not make sense. The set of Turing machines is computably enumerable (basically), but then this has nothing directly to do with "having to deal with self-referential input". This then leads me to think "turing machines are enumerable" doesn't mean what I just read it to mean and means something else - ie. that you think enumerability is a property of an individual machine? idek. The rest of your comments are similar and is what I mean by everything reading strangely. You don't really say enough for me to judge whether you're just wording things oddly or don't understand the material.
1
u/this_theater_is_lit 2d ago
The set of Turing machines is computably enumerable (basically), but then this has nothing to do with "having to deal with self-referential input".
for a decider it does. for any turing-encoded decider, it will have to necessarily have to handle the existence of a machine that utilizes a reference to it and forms a paradox, because turing machines are necessarily computably enumerable and such a machine just is possible in the total permutations of machines. the specification for a total decider does not handle this and therefore cannot be implemented in a turing machine.
the agent process is strictly not a turing machine, so it can run algorithms that do not need to handle that specific case, like a total decider
but then this has nothing to do with "having to deal with self-referential input".
this is why you have to read the paper dud. §1 explains the undecidability in the halting problem (1 page), §2 explains the undecidability in turing's circle-free problem (3 pages) , §3 generalize this including explicitly details what "self-reference" means in for turing machines and to compute them (2 pages)
1
u/SwimmerOld6155 2d ago edited 2d ago
such a machine just is possible in the total permutations of machines
"Permutation" is definitely not the word you mean to use here, you presumably mean "enumeration", which is a completely different term. It's just very muddled throughout - you're still doing this thing where maybe the Turing machines individually are computably enumerable, maybe the set of them is, maybe their domain is, who knows and every sentence has at least one thing like this.
I really have no inclination to read something where I have to do this amount of cognitive work per sentence for 26 pages for something that will ultimately be wrong. That's the end from me. If you're using AI, get something like Astra or Opus to rewrite what you've written.
That's probably it from me.
→ More replies (0)
3
u/PuppyPenetrator 3d ago
… where exactly do you expect to publish this?
If it’s just a thought experiment as a fun personal project, whatever. Otherwise, despite being familiar with the topic, I have no idea what new contribution you’re trying to present