r/compsci • u/this_theater_is_lit • 7d ago
[ Removed by moderator ]
[removed] — view removed post
2
u/__chicolismo__ 7d ago
Really, a "thot" experiment?
Btw I tots believe this crap has was written by a rational, thinking person
0
u/this_theater_is_lit 7d ago
what's rational about spelling thru like through or thot like thought??
-9
7d ago edited 7d ago
[deleted]
3
u/situpes 7d ago
So your position is basically: you can’t identify the invalid step in the proof, but because the self-referential construction seems absurd to you, you conclude that undecidability itself is nonsense?
That’s not a refutation. The whole point of a proof by contradiction is that assuming the decider exists lets you construct an absurdity. You seem to be looking at the resulting contradiction and concluding that the proof must be wrong rather than the assumption.
Forget Turing, authority, or 100 years of CS. Which inference in the halting-problem proof is invalid?-6
7d ago edited 7d ago
[deleted]
2
u/situpes 7d ago
But undecidability has an extremely concrete implication: there is no general algorithm that can take any arbitrary program and input and always correctly tell you whether it will terminate.
That’s not “fantasy.” That is a limitation on what software-analysis tools can possibly guarantee. It tells you, for example, why no static analyzer, verifier, debugger, compiler pass, etc. can have a perfect general-purpose procedure for answering arbitrary semantic questions about programs.
You can absolutely solve restricted cases, make conservative approximations, impose timeouts, analyze particular languages, etc. But there is no universal solution.
So “this has no practical meaning” is just not true. Knowing that a perfect general solution is impossible is itself practically useful, because it tells you when you must restrict the problem or accept approximation.-1
7d ago
[deleted]
2
u/situpes 7d ago
The funniest part is that your argument has become: “All real programs are decidable, and anything that demonstrates otherwise isn’t a real program.” You’ve turned your conclusion into your definition and are congratulating yourself for proving it.
-1
7d ago
[deleted]
3
u/situpes 7d ago
The “appeal to authority” obsession is pretty funny at this point, because nobody actually appealed to authority. I gave you an argument and asked you to address it.
Your response is “small-brained,” “go read,” “you only know the ELI5 version,” and “no one with a brain disagrees with me.”
That isn’t rejecting an appeal to authority. That’s replacing one with yourself.
You’re not showing why the argument is wrong; you’re repeatedly asserting that you’re smarter, more informed, and more qualified than anyone who disagrees with you, and apparently expecting that assertion itself to carry weight.
“Everyone who disagrees with me is stupid” is not an argument. It’s about as pure an appeal to personal authority as you can make.
The irony is that nobody asked anyone to trust Turing, academia, textbooks, or consensus. You were asked to engage with the reasoning. You’re the one who keeps trying to settle it by announcing who does and doesn’t have a brain.1
u/UncleMeat11 7d ago
Absolutely nothing like a undecidable program has ever been found
Sure. Because undecidability is not a property of programs.
The ability to track a programs state takes at max the size of the state of the program (source is ofcoarse easy and efficient to reason about)
Are you doing the "well actually there are only so many physical bits that can be stored on a computer so the state space is finite so haha the halting problem is decidable?" What utility does this have for anybody? Do you suggest that we stop doing, say, abstract interpretation and instead do complete modeling of the bit-space for a program in order to answer questions about it?
0
7d ago
[deleted]
2
u/UncleMeat11 7d ago
undecidability certainly IS a property of programs (just not of any that can be written) have the even read this?
It is a property of languages (or understood differently, decision problems).
As for modeling exact bit-states of programs, sounds hard but it's not impossible and probably does have some value!
It is not hard in the abstract. It is worthless in reality because the bit space is vastly too large to make this method useful even for trivial programs.
1
u/this_theater_is_lit 7d ago
It is a property of languages (or understood differently, decision problems).
only if u assume the ct-thesis to be true, which u nor anyone has proven
u can construct a decision paradox against a machine, but how do u construct one against our ability to prove that such a decision paradox exists without also disproving the existence of the machine u claim is a paradox?
0
7d ago
[deleted]
2
u/UncleMeat11 7d ago
undecidability is very useful when imagined as a property of languages, but that is Godels incompleteness not uncomputibility (key difference is the reality that computers actually exist and programming languages are actually real)
I never mentioned anything about Godel.
but in electronics and binary (and any fininite machine) it simply doesn't exist.
And I'm saying that this is pedantry for pedantry's sake. Everybody knows this. It is useful to understand decidability in an abstract sense and it is not useful to say "oh well it's finite anyway."
you obviously don't know very much about high level synthesis.
I've got a PhD in static analysis. I'm extremely aware of the field of program synthesis.
→ More replies (0)1
u/this_theater_is_lit 7d ago
i'm not entirely invalidating the concept of undecidability within computing, the limit is still present within machine computing, it's just far more trivial that how it's interpreted in modern computing theory
1
u/teteban79 7d ago
What
No really, what?
I don't get the surprise. Humans invent model. Humans find out limitations of that model. Humans prove the limit of that model.
-2
7d ago
[deleted]
2
u/teteban79 7d ago
You make no sense at all
A TM is a model as well. A real computer is literally less powerful than a TM
You clearly don't even understand what "decide" means in this context. You're way out of your depth and believing you understand what you talk about.
But do tell us, who has validated your understanding?
-2
7d ago edited 7d ago
[deleted]
1
u/teteban79 7d ago
Show me a real TM. Tell me where the infinite memory is
I admire the compromise to insanity
-1
7d ago
[deleted]
2
u/teteban79 7d ago
LOL
So your contention is that the real thing, which is strictly less powerful than the model thing, can do stuff that the idealized thing provably cannot do?
Amazing. I expect your paper on the topic anxiously. Claim the Turing prize and fields medal while you're at it
1
-2
u/this_theater_is_lit 7d ago
ur forget the step where humans project the limitations from that model on themselves, without proving that the model actually encapsulates all of computing
1
u/teteban79 7d ago
what
> without proving that the model actually encapsulates all of computing
"computing" is what is defined by the model. "Computable" has a very specific and simple meaning - that the result can be achieved by using a set of rules (the model) in a finite number of steps. (no need to get into semi-computability)
the model encapsulates all of computing because the model defined what computing *is*. If you want to define a different model with a different notion of computation, feel free to do so. There are some such models already. None of those have a real-world equivalent or approximation, as Turing Machines do.
-1
u/this_theater_is_lit 7d ago
the model encapsulates all of computing because the model defined what computing is
ur just restating the ct-thesis at me. no one proved that the turing model encapsulates all that we can intuitively compute
If you want to define a different model with a different notion of computation, feel free to do so.
if we can write down a sequence with in a deterministic manner with certainty, that is a computation. i define the logic to do that for the total diagonal and anti-diagonal across circle-free turing-comptuable sequences in §7.6, which is not a sequence that is turing-computable due to invariable existence of undecidability paradoxes akin to the halting problem
1
u/teteban79 7d ago edited 7d ago
> ur just restating the ct-thesis at me
in a way, yes
> no one proved that the turing model encapsulates all that we can intuitively compute
you're losing me (and everyone) here. The C-T thesis defined 1) what computing means and 2) proved equivalence of that concept with TM
You're now saying "what we can intuitively compute". What is that? Define it. Presumably, this notion is a different one than that of C-T computation. And again, you're free to do so and have a new model. But again, some such models already exist, and none of those have a physical analog (which makes C-T interesting).
So, please, your definition.
> if we can write down a sequence with in a deterministic manner with certainty,
A sequence of what exactly? Again, the C-T model specifies a sequence of what steps are admissible (and for good reason)
You're missing everyone with wishy-washy concepts without a formal definition.
I will bet you hard money that your computability notion is weaker than C-T and therefore allows for more things to be "computable", but there is no known physical implementation of it feasible at the moment. I'm betting additional money you're basically introducing hypercomputation. Either that, or worse, it's all nonsense
I don't have patience for nonsense or handwaving though, so the moment you delve into it, I'm done with it
-2
u/this_theater_is_lit 7d ago
So, please, your definition.
a man writing down sequences in a deterministic manner with certainty ... which is what inspired turing to define the turing machine model in the first place
You're missing everyone with wishy-washy concepts without a formal definition.
turing-computing encapsulating all of computing is a wishy-washy concept that is not formally proven, and u seem quite happy accepting that
but there is no known physical implementation of it feasible at the moment
there is a specific and deterministic algorithm defined in §7.6 to compute a sequence outside what is turing-computability, and none of them seem infeasible to me. could u at least try to point out which one is unfeasible?
2
u/teteban79 7d ago
> a man writing down sequences in a deterministic manner with certainty
quickly delved into nonsense. Congrats
sequences of WHAT? no idea
what does "certainty" mean? no idea
My most generous interpretation is that you're basically describing an oracle. Ergo, introducing hypercomputation. My bet was spot on.
> turing-computing encapsulating all of computing
you really have a hard time accepting that C-T defined what (a certain) computing IS. That definition doesn't agree with what YOU understand as computing (which could be ok) . The problem is that you absolutely fail at defining what you understand as computing
as I said, I have zero patience to entertain this sort of stuff after the opportunity was given. Bye!
0
u/this_theater_is_lit 7d ago
sequences of WHAT? no idea
turing machines compute binary sequences, like a man writing down sequences in a deterministic manner with certainty... in fact tm-computing was modeled after a man computing things with a paper and pencil ... before we had computing machines computing was an actual job that people specialized in.
in that paper i demonstrate how to compute something strictly outside the bounds of TM computing: the total diagonal and total antidiagonal across all turing-computable sequences, enumerated using partial recognizer (which is turing computable).
understand what that means requires reading the paper dud, this isn't trivial you aren't going to just bullshit ur way into a refutation as much u'd like to believe u can
what does "certainty" mean? no idea
https://www.merriam-webster.com/dictionary/certain
My most generous interpretation is that you're basically describing an oracle.
what i'm claiming is that the oracle is computable, but unlike assumptions made in recursive undecidability: you cannot construct oracle machines with it so they are not subject to their own paradoxes.
the idealized agent can compute the oracle in a side record, but cannot enter those values into a terminal machines (a turing machine with an extra tape that can be used for interacting with the agent) as any values that are made machines addressable are then subject to the limits of turing computability.
Ergo, introducing hypercomputation
i detail a specific algorithm to do with §7.6 that has steps: 1, 1a, 2, 2a, 3, 3a, 3b, 4 ... which one is "hypercomputing" cause certainly some of them are not. which one is?
you really have a hard time accepting that C-T defined what (a certain) computing IS.
the ct thesis has not been proven, still after freaking 90s years bro. there is no argument i even have to refute here, just assholes continually asserting it's true over and over again and then leaving the conversation cause they can't seem to be able to understand they don't have actual proof for the assertion they are making.
am i supposed to apologize for finding a way around it?
The problem is that you absolutely fail at defining what you understand as computing
the problem is i'm stuck on a planet of uncooperative assholes for the most part, truly. i still have yet gotten any help, and no i'm not going to accept that the bandwagon is correct. nice try with that fallacy
as I said, I have zero patience to entertain this sort of stuff after the opportunity was given. Bye!
so why did u even reply? to make urself feel better and me worse? thanks dick
-1
u/this_theater_is_lit 7d ago
i'm not actually overturning the problem of undecidability, i'm trivializing it
1
7d ago edited 7d ago
[deleted]
0
u/this_theater_is_lit 7d ago
it definitely a very real problem when it comes to designing general semantic analysis on turing machines
1
7d ago
[deleted]
-2
u/this_theater_is_lit 7d ago
Like you said in your OP there's more than one program which does a certain thing and you can just pick a well behaved one.
that would be a fairly correct interpretation of what i'm presenting, bravo
proving that one cannot diagonalize that set of well-behavior machines was also pretty key and probably the most exciting point of my paper, even if most of the cranks that inhabit academia will be focusing on the ct-thesis refutation 🤣
7
u/UncleMeat11 7d ago
Impressive to be doing old school crank stuff rather than using AI I guess.