So the Halting problem is all about neither returning "yes" or "no"? Then the analyzer could simply loop forever... the stupid thing is that the analyzer can know it's impossible, yet the definition of the problem doesn't allow it to answer. I think the problem is the Halting problem, just with the Turing intelligence test. What happens if you switch AI with the judges? Then humans become the non-intelligent because they don't live up to the potential of AI.
This is totally bogus. You dismiss finite state machines out of hand. The filthy liar program fails in most languages due to resource exhaustion. You completely missed the point of stating your assumptions in a proof.
@jok2000 Good eye. You noticed it wasn't a formal proof. What gave it away? Was it the cartoons? Finite State Machines? Yeah, and I dismiss pushdown automata too, but maybe you've got an FSM that solves the halting problem. Perhaps I shouldn't dismiss them? Filthy Liar's failure has nothing to do with resource exhaustion, it has to do with it's use of impossible code, namely its call to fantasy system B. If you're a pedant, lighten up. If you're a P=NP crank, take a hike.
@kjlg74 "P=NP crank". I'm a philosopher. I have in fact read books on cranks. Mostly mathematical cranks, however, as I used to like math puzzles. Occasionally I like to examine the psychology of random academics. The video is highly suggestive that your earlier degree is in the Arts& Science arena and not the engineering arena. Good luck with artificial life. You'll need it.
@jok2000 You're correct about my degrees, and I'm glad you're not only not a crank but also familiar with what I mean by that. I was a little shocked when I first encountered comp. sci. and math cranks - I knew they were plentiful in bio, chem, med, etc. I've also read books on cranks, but usually the creationist or quack-med kind. It seems we share an interest in that regard, even if we disagree substantially regarding this video's contents. Ciao
@Battlewench Thanks for taking the time to let me know :) I'm glad you liked it!
What kind of reading do you do in that course? If the book "Goedel, Escher, Bach" isn't on list, I highly recommend it. One of my favorite computing/math/philosophy/AI books (it's quite a crazy mix of topics).
This series was written and produced by someone with great animation skills and a flare for the cinematic. They do however lack extremely the ability to pursue legitimate computational possibility. Theirs is a world where problems are given court over solutions and it is always demarkated by their hollow mean spirited war cry of 'You cannot!'. Please broaden your mind or stick to animation. It is a shame to see your talent wasted as is. My email is marty dot musatov at gmail dot com, you idiot.
I think, even if a program deliberately checks for certain situations - like whether it was fed a liar program - it would still have to give an answer, and it would still be immediately contradicted.
The proof just shows that it is not possible to solve the halting question for *all* conceivable computer programs. It doesn't say anything about whether the scenario in the video is the only way such problems arise. I suspect it's not the only way but I don't really know.
No, no I don't mean that the program B checks for certain situations. I meant: what if filthy liar doesn't know about B (which is usually the case). What if filthy liar only has input to work on. in that case FL can't feed itself to B and can't predict whether to go into a loop or halt (i.e. lie) - if you don't know the truth you can't lie =)
But I suspect the halting problem is always going to be unsolvable in general.
I think I see what you mean. In the video FL and B are described as if they were meant to be separate things but only to try to keep it simple. In principle, you could incorporate whatever it is that B does inside FL. Alternatively you could have FL take 3 parameters (then it wouldn't know about B at all, but you could give it B as a third argument - i.e. FL(x,y,z) = opposite(z(x,y)), and then the proof would involve executing FL(FL,FL,B), but then B would need 3 arguments instead...
A real life example of similar programs occured to me: antivirus software. AV progs use virus databases and heuristic algorithms to detect a virus. When writing a new virus I can use the current updated AV as my program B, and feed myself to it - then modify myself so as to lie to B (I'm not a virus). But after the undetectable virus comes out, the AV database or heuristics are modified to detect the virus regardless.
So really it's a case of being ahead of the game.
i think the halting problem is the same kind of problem as to try to build a machine that can predict the future.. such a machine fails at the moment where it has to predict its own output. so i think the halting problem is only a problem if the algorithm gets itself as input
Good point, although I suspect the problem is even more general - but I'm no expert in this particular area. I could imagine, for example, 2 different algorithms that accomplish the task in different ways, and they might be made to fail by following a scheme where one is applied to the other. I suspect you can tease that out into all sorts of convoluted scenarios where it's not clear at all that a program is attempting to predict its own future.
The idea that a program could give the right answer for *any* program+input pair is technically disproved, though. You could probably make an infinite-loop-detector under certain types of constraints on the input program, but I don't know how severe those restrictions would have to be. I suspect they would be *quite* severe indeed, but I don't really know.
i think the halting problem is limited to inputs that uses the analyzer algorithm itself.. for example: if you build a scenario like in the video and put the filthy liar program into halting analyzer it will compute the correct output. depending on what the analyzer inside outputted. so i think the problem is limited to analyizing itself
Thanks! I have a couple more Alice-Bob-Eve video ideas waiting to be done at some point. I was watching Greg's channel a while back and thought "that would be an awesome voice for the god character!" - and he was kind enough to give it a go when I suggested it to him. I agree, he did a great job :)
Cold weather? Where are you? Snow here in Connecticut is coming down in bucketloads!
One state above...Worcester, MA . The heavy snow is just starting here, we shouldn't get as much as you, but it will be more than enough...for me anyway!
I think the series will be a hit, great idea going with Greg, been a fan of his work for sometime now. You've gained a new sub, I'll be looking forward to more of your work...Rob
y does it enter an infinite loop after outputting yes?
giza182 3 months ago
Why does Cypherus have an Aussie accent?
ClericAgent 8 months ago
what if i run B with two different inputs?
B(x,y) only with x!=y
would the problem become decidable?
9H0A0L0 9 months ago
@9H0A0L0 no
loernIt 3 months ago
So the Halting problem is all about neither returning "yes" or "no"? Then the analyzer could simply loop forever... the stupid thing is that the analyzer can know it's impossible, yet the definition of the problem doesn't allow it to answer. I think the problem is the Halting problem, just with the Turing intelligence test. What happens if you switch AI with the judges? Then humans become the non-intelligent because they don't live up to the potential of AI.
bvssvni 10 months ago
I bet I can solve it
manrayer88 10 months ago
Thank you for this!, It helped me get the point of the halting problem :D
PanchoQV 1 year ago
@PanchoQV You're welcome! Thanks for the comment :)
kjlg74 1 year ago
o no eve is going to get child porn on her comp....
ltshinta 1 year ago
This is totally bogus. You dismiss finite state machines out of hand. The filthy liar program fails in most languages due to resource exhaustion. You completely missed the point of stating your assumptions in a proof.
jok2000 1 year ago
@jok2000 Good eye. You noticed it wasn't a formal proof. What gave it away? Was it the cartoons? Finite State Machines? Yeah, and I dismiss pushdown automata too, but maybe you've got an FSM that solves the halting problem. Perhaps I shouldn't dismiss them? Filthy Liar's failure has nothing to do with resource exhaustion, it has to do with it's use of impossible code, namely its call to fantasy system B. If you're a pedant, lighten up. If you're a P=NP crank, take a hike.
kjlg74 1 year ago 3
@kjlg74 "P=NP crank". I'm a philosopher. I have in fact read books on cranks. Mostly mathematical cranks, however, as I used to like math puzzles. Occasionally I like to examine the psychology of random academics. The video is highly suggestive that your earlier degree is in the Arts& Science arena and not the engineering arena. Good luck with artificial life. You'll need it.
jok2000 1 year ago
@jok2000 You're correct about my degrees, and I'm glad you're not only not a crank but also familiar with what I mean by that. I was a little shocked when I first encountered comp. sci. and math cranks - I knew they were plentiful in bio, chem, med, etc. I've also read books on cranks, but usually the creationist or quack-med kind. It seems we share an interest in that regard, even if we disagree substantially regarding this video's contents. Ciao
kjlg74 1 year ago
that was lulzy
Battlewench 1 year ago 2
@Battlewench Thanks :) (I think)
kjlg74 1 year ago
@kjlg74 Haha yeah, in a good way. I'm doing a course in the philosophy of computing, this is by far the best explanation I've heard.
Battlewench 1 year ago
@Battlewench Thanks for taking the time to let me know :) I'm glad you liked it!
What kind of reading do you do in that course? If the book "Goedel, Escher, Bach" isn't on list, I highly recommend it. One of my favorite computing/math/philosophy/AI books (it's quite a crazy mix of topics).
Cheers!
kjlg74 1 year ago
@kjlg74 Haven't read it, but thanks, I'll definitely have a look!
Battlewench 1 year ago
This series was written and produced by someone with great animation skills and a flare for the cinematic. They do however lack extremely the ability to pursue legitimate computational possibility. Theirs is a world where problems are given court over solutions and it is always demarkated by their hollow mean spirited war cry of 'You cannot!'. Please broaden your mind or stick to animation. It is a shame to see your talent wasted as is. My email is marty dot musatov at gmail dot com, you idiot.
martymusatov 1 year ago
badass
charliebaird13 1 year ago
@charliebaird13 Hee hee! Thanks :)
kjlg74 1 year ago
Um.. just an idea: is this valid even if the "lying" program doesn't know about the testing program discovering whether it will halt?
Maybe the test program can look to see if the lier references itself?
Although I get the halting problem I mean computer programs have access to random data as well, which can lead to cyclic behaviour.
Sigh.. must study.
8DX 2 years ago
I think, even if a program deliberately checks for certain situations - like whether it was fed a liar program - it would still have to give an answer, and it would still be immediately contradicted.
The proof just shows that it is not possible to solve the halting question for *all* conceivable computer programs. It doesn't say anything about whether the scenario in the video is the only way such problems arise. I suspect it's not the only way but I don't really know.
kjlg74 2 years ago
No, no I don't mean that the program B checks for certain situations. I meant: what if filthy liar doesn't know about B (which is usually the case). What if filthy liar only has input to work on. in that case FL can't feed itself to B and can't predict whether to go into a loop or halt (i.e. lie) - if you don't know the truth you can't lie =)
But I suspect the halting problem is always going to be unsolvable in general.
Great vid!
8DX 2 years ago
Thanks :)
I think I see what you mean. In the video FL and B are described as if they were meant to be separate things but only to try to keep it simple. In principle, you could incorporate whatever it is that B does inside FL. Alternatively you could have FL take 3 parameters (then it wouldn't know about B at all, but you could give it B as a third argument - i.e. FL(x,y,z) = opposite(z(x,y)), and then the proof would involve executing FL(FL,FL,B), but then B would need 3 arguments instead...
kjlg74 2 years ago
...of 2, and there are even ways around that, actually.
Ah, well, we're probably needlessly complicating things :P
kjlg74 2 years ago
Forget the rambling I did above, the more I think about it, the more I think it might not help with a proof that B is impossible anyway.
kjlg74 2 years ago
(deleted my comment oops)
A real life example of similar programs occured to me: antivirus software. AV progs use virus databases and heuristic algorithms to detect a virus. When writing a new virus I can use the current updated AV as my program B, and feed myself to it - then modify myself so as to lie to B (I'm not a virus). But after the undetectable virus comes out, the AV database or heuristics are modified to detect the virus regardless.
So really it's a case of being ahead of the game.
8DX 2 years ago
I wouldn't be surprised is something like that actually happens from time to time in the AV world.
kjlg74 2 years ago
i think the halting problem is the same kind of problem as to try to build a machine that can predict the future.. such a machine fails at the moment where it has to predict its own output. so i think the halting problem is only a problem if the algorithm gets itself as input
ecreif 2 years ago
Good point, although I suspect the problem is even more general - but I'm no expert in this particular area. I could imagine, for example, 2 different algorithms that accomplish the task in different ways, and they might be made to fail by following a scheme where one is applied to the other. I suspect you can tease that out into all sorts of convoluted scenarios where it's not clear at all that a program is attempting to predict its own future.
..continued..
kjlg74 2 years ago
The idea that a program could give the right answer for *any* program+input pair is technically disproved, though. You could probably make an infinite-loop-detector under certain types of constraints on the input program, but I don't know how severe those restrictions would have to be. I suspect they would be *quite* severe indeed, but I don't really know.
kjlg74 2 years ago
i think the halting problem is limited to inputs that uses the analyzer algorithm itself.. for example: if you build a scenario like in the video and put the filthy liar program into halting analyzer it will compute the correct output. depending on what the analyzer inside outputted. so i think the problem is limited to analyizing itself
ecreif 2 years ago
Well, I don't know if there's a proof that you're wrong, but I bet that a proof that you're right would be *really* difficult ;)
kjlg74 2 years ago
Well, it was a tough decision. I'm glad you guys gave me so many options to consider, though :)
kjlg74 2 years ago
wierd ending :P
Gladdig 2 years ago
In a good way, I hope :)
kjlg74 2 years ago
Great video series! 1GOD1JESUS pulled the spiritual being off to a tee...5*
I am burning a little for watching it...but I can use the heat, it's cold as hell here... ;)
rgman66 2 years ago
Thanks! I have a couple more Alice-Bob-Eve video ideas waiting to be done at some point. I was watching Greg's channel a while back and thought "that would be an awesome voice for the god character!" - and he was kind enough to give it a go when I suggested it to him. I agree, he did a great job :)
Cold weather? Where are you? Snow here in Connecticut is coming down in bucketloads!
kjlg74 2 years ago
One state above...Worcester, MA . The heavy snow is just starting here, we shouldn't get as much as you, but it will be more than enough...for me anyway!
I think the series will be a hit, great idea going with Greg, been a fan of his work for sometime now. You've gained a new sub, I'll be looking forward to more of your work...Rob
rgman66 2 years ago
Thanks!
I'm on my bicycle in this snow today, so if I never post any videos again it's probably because I never made it home :)
kjlg74 2 years ago
Just steer clear of plows & snowtards, (term of endearment), and it could be fun :D
rgman66 2 years ago
Cypherus... allot like cypher eh ;D
TheReasonWhyGuy 2 years ago
Yep :)
kjlg74 2 years ago
Cypherus sounds alot like 1GOD1JESUS.... coincidence? I think not...
joshcena33 2 years ago
Definitely a strong resemblance!
kjlg74 2 years ago
Awesome!
1GOD1JESUS 2 years ago
Couldn't have done it without'cha! :D
kjlg74 2 years ago
Bob was a bit slow. ;-)
CousinoMacul 2 years ago
He did get a little carried away with his techno-babble when he should have just shut up :)
kjlg74 2 years ago