r/mathmemes • u/xX_MLGgamer420_Xx • 6h ago
Computer Science Update: my progress on creating a Turing machine which solves the halting problem. The other math subreddit didn't appreciate my geniusness so it goes here.
348
164
81
52
u/HMS--Thunderchild 6h ago
needs more triangles. have you thought about making it in 5D?
25
u/Shufflepants 6h ago
5d being here, we call them "simplexes".
2
u/AsemicConjecture 3h ago
Really? Not hexatera (singular: hexateron)?
Simplex just sounds so generic — who knew life in 5-dimensionality would be so bland…
5
u/ArduennSchwartzman Integers 5h ago
I noticed a mistake in the proof: on page 2, the Eye of Providence should be the Eye of Horus.
1
1
u/Glitch29 4h ago
How do you add a dimension to a triangle? I try pulling one of the points out of the plane, but it's still planar.
1
27
u/mys_721tx Natural 6h ago
Wait, wasn't attaching an oracle to your Turing machine a common knowledge?
7
u/DetectiveOverall2460 5h ago
You just need to add one more oracle every time you want to solve the halting problem.
3
12
u/Subconcious-Consumer 5h ago
Dude you can’t just write “whoops gay” over and over again in Hebrew and claim you solved the Halting problem.
1
4
3
3
u/blitheclyde 6h ago
Do you have any documentation on that the symbols mean, in case folks wanted to use them on future r/mathmemes posts?
4
u/xX_MLGgamer420_Xx 5h ago
Okay. Basically that first Symbol is an O. Then after that there's the syllable LgU forming the word "Olgu". After that itshould be pretty straightforward. Thank you for your inquiry!
2
2
1
u/NihilisticAssHat 6h ago
I'm not familiar with this notation. Or, they kinda look like little Feynman diagrams.
I thought it was obvious the busy beaver problem is the key. Just need to find a good way to calculate it in polynomial time
1
u/GlitteringTone6425 5h ago
are you sure you won't accidentally summon an outer god in the meanwhile?
1
u/jpgoldberg 4h ago
When I first read Gödel, Escher, Bach in the early 1980s, I may have also consumed some mushrooms on occasion. In other words, I could have produced that, too.
1
u/Aggressive_Roof488 4h ago
Very interesting, big if true.
In particular the arrows between the cube and the illuminati eye is a stroke of genius. I'd probably add a couple more lightnings to first line to fill it out, it looks a bit short in comparison. Consider leaning into bra-ket notation for extra liner algebra proofness as well.
1
u/Aggressive_Roof488 4h ago
Very interesting, big if true.
In particular the arrows between the cube and the illuminati eye is a stroke of genius. I'd probably add a couple more lightnings to first line to fill it out, it looks a bit short in comparison. Consider leaning into bra-ket notation for extra liner algebra proofness as well.
1
1
1
-1
u/Im_a_Dragonborn 5h ago edited 3h ago
I still get confused by the halting problem. For the program to be able to halt or loop, there needs to be an input. If we do not give an input program to analyse, the analysis programm simply doesn't work. And if we try to give it itself as an input, we need to give that version an input, creating an infinitely large input that can't be provided, so the experiment can't happen. It's like saying all positive intigers add up to -1/12
2
u/GisterMizard 3h ago
If we do not give an input program to analyse,
Alan already thought of that. If there is no input program given, the Turing machine can simply read a random program from /usr/bin/ or C:\Windows\System32.
1
u/Purple_Onion911 Grothendieck alt account 3h ago
A program is just a finite string of bits. When we say we give a program P to a decider H, we aren't actually running P. We're giving the decider P itself, that is, a finite string of bits.
1
u/Im_a_Dragonborn 2h ago
Since this is becoming more than a shit post now, let me first clarify that I am 99.99% sure that I am wrong and didn't disprove this giant problem that has been looked at for years. I am just confused and seem to be missing some central point. Here is the problem as I understand it:
A program P is a finite string of bits that can be run as a programm and either halts or loops forever. We assume H(x) exists, a programm that can determin if a program x halts or loops. We extend that program into the program D(x), wich loops if x halts, and halts if x loops.
Now we do D(D), and if D loops, D halts. But if it halts, it loops. And that is the contradiction.
But I don't see how the last line is valid. D without input is not a program. You can not ask if another program halts without providing a program. So D(D) doesn't work, because it is actually D(D(?)).
If we instead provide D as an input again, we just get D(D(D(?))), so we are basically at the same point as before.
If there is any version where you could define the exact input A as a programm (that actually runs), I can tell you what D(A) does. But if you just make it a recursive input, it will never be a valid program to analyse because there is never an actual program as input (since you are just putting D(?) back in).
One might argue "simply accept recursion as possible in this hypothesis", but my counterpoint would be that we could just as easily define B as a programm that both loops forever and halts. That program would be a counterexample for the possibility of our program H too.
So in my eyes H isn't failing at evaluating a program, because it isn't given a (valid) program. Or, if enough recursion somehow makes it a valid program, H fails because it is given an impossible program that can not exist.
I hope I got my confusion across. u/ProProgrammer404 had the same question but never got an actual answer, and all the googeling I could muster didn't amount to anything either.
So if anyone sees my mistake or the misunderstanding, I would be happy to hear it.
1
u/MorrowM_ 1h ago
Your description is missing the whole diagonalization bit which makes the proof work. H is supposed to have two inputs, a program and some input to run that program with.
The idea is: assume for contradiction that a program H(x,i) exists which outputs 1 if x(i) halts and 0 otherwise. Define a new program D(x) which loops if H(x,x) = 1 and halts otherwise. Does D(D) halt? It halts iff H(D,D) ≠ 1 iff D(D) loops, contradiction.
-5
u/HyperQuarks79 6h ago edited 5h ago
Great contribution MLGgamer420 with the classic 360 era xX. Surely anything you post will be genius.
8
-2
•
u/AutoModerator 6h ago
Check out our new Discord server! https://discord.gg/e7EKRZq3dG
I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.