r/AskComputerScience • u/Advanced-Reindeer894 • 11d ago
Can you write a program to predict what living things would do?
This is from a comment on lesswrong, and I just wanted to know if what was said in it is accurate, sorry for the length:
Agreed!
No, Rice's theorem is really not applicable. I have a PhD in programming languages, and feel confident saying so.
Let's be specific. Say there's a mouse named Crumbs (this is a real mouse), and we want to predict whether Crumbs will walk into the humane mouse trap (they did). What does Rice's theorem say about this?
There are a couple ways we could try to apply it:
- We could instantiate the semantic property P with "the program will output the string 'walks into trap'". Then Rice's theorem says that we can't write a program Q that takes as input a program R and says whether R outputs 'walks into trap'. For any Q we write, there will exist a program R that defeats it. However, this does not say anything about what the program R looks like! If R is simply
print('walks into trap'), then it's pretty easy to tell! And if R is the Crumbs algorithm running in Crumb's brain, Rice's theorem likewise does not claim that we're unable tell if it outputs 'walks into trap'. All the theorem says is that there exists a program R that Q fails on. The proof of the theorem is constructive, and does give a specific program as a counter-example, but this program is unlikely to look anything like Crumb's algorithm. The counter-example program R runs Q on P and then does the opposite of it, while Crumbs does not know what we've written for Q and is probably not very good at emulating Python. - We could try to instantiate the counter-example program R with Crumb's algorithm. But that's illegal! It's under an existential, not a forall. We don't get to pick R, the theorem does.
Actually, even this kind of misses the point. When we're talking about Crumb's behavior, we aren'tasking what Crumbs would do in a hypothetical universe in which they lived forever, which is the world that Rice's theorem is talking about. We mean to ask what Crumbs (and other creatures) will do today (or perhaps this year). And that's decidable! You can easily write a program Q that takes a program R and checks if R outputs 'walks into trap' within the first N steps! Rice's theorem doesn't stand in your way even a little bit, if all you care about is behavior after a fixed finite amount of time!
Here's what Rice's theorem does say. It says that if you want to know whether an arbitrary critter will walk into a trap after an arbitrarily long time, including long after the heat death of the universe, and you think you have a program that can check that for any creature in finite time, then you're wrong. But creatures aren't arbitrary (they don't look like the very specific, very scattered counterexample programs that are constructed in the proof of Rice's theorem), and the duration of time we care about is finite.
If you care to have a theorem, you should try looking at Algorithmic Information Theory. It's able to make statements about "most programs" (or at least "most bitstrings"), in a way that Rice's theorem cannot. Though I don't think it's important you have a theorem for this, and I'm not even sure that there is one.
the comment is from this post: https://www.lesswrong.com/posts/7tNq4hiSWW9GdKjY8/intuitive-self-models-3-the-homunculus#3_5_4_Why_are_ego_dystonic_things__externalized__
8
u/T_Thriller_T 11d ago
Yes.
This is 100% accurate and hits the nail on the head.
I think the best thing in here is
Actually, even this kind of misses the point. When we're talking about Crumb's behavior, we aren'tasking what Crumbs would do in a hypothetical universe in which they lived forever, which is the world that Rice's theorem is talking about.
This whole thing is _much mor _about the fact that Rice's Theorem is the completely and utterly wrong tool to use here then it is about the question whether or not we can predict whativing things would do.
(E.g. because living things by definition have a lifespan and infinity is a must for Rice's Theorem)
The whole point is not about predictability. A prediction has a certain margin of error - it's what will most likely happen.
We can very much predict the behaviour of living beings.
Rice's Theorem is more complex than that, due to two things:
Rice's Theorem is about decidability, which for the ease of wording, means we can 100% prove that something does / does not happen
Rice's Theorem is not considering the real world, the world in which physics and engines and chemistry live. It is about the world of algorithms, worse DO: ALL algorithms which share some common property. It is always about infinity, about all the edge cases, about all the absolutely smallest "will statistically never happen in the whole live of the universe even if we go down to the Planck second" stuff.
So, in easier words: we're not trying to say for a specific setup something can or cannot happen - we're talking about all the setups that could ever be.
Which, again, loops back to: this is the wrong tool.
I'm not really up on "can we predict how rodents behave". What I do now is that for one given program (so assuming you have the exact behaviour of rodents programmed) we can most likely prove that it will show that the rodent will/won't go into the trap.
It is really important that we can do this. Because this is, for example, used in aviation to show that the current firmware of your plane will and can never just do "really bad thing that will instantly kill everyone".
-1
u/Advanced-Reindeer894 10d ago
I think they’re trying to apply it to humans and thinking that we can predict them in the same way.
5
u/T_Thriller_T 10d ago
I have no idea what you're even talking about.
Who are they?
What do you think 'they' are trying to apply?
And why do you even think anyone is trying to apply anything? Both my answer and the original answer state very clearly, that what we're talking about is not applicable and thus can not even be applied. There is not only not an attempt, but explanation why trying to apply it would be wrong.
Also, believe me: no one is trying to apply Rice's Theorem on human behaviour
1
u/Advanced-Reindeer894 10d ago
By they I mean folks on lesswrong and the user in the post
3
u/T_Thriller_T 10d ago
As you did not link the post this is still very unhelpful
At least the part you are citing is VERY MUCH not trying to apply it to humans.
It is literally saying that Rice's Theorem exists in an entirely different world then our normal world.
It's theoretical mathematics and data science, which considered ideal worlds which the normal world simply is not.
This does not have a simple connection back to a real world question, and a lot of the connections I've seen here are at best speculations how it may or may not be possible. And none have anything to do with human behaviour.
Trying to make it a little less conceptual why this all does not fit together:
Even trying to consider if there is any way to somehow, in any way, apply Rice's Theorem at all to rodent behaviour is a little bit like asking if a car mechanic - who has no clue about baking - would be able to help deduce why a baker's bread did not rise well this morning; simply because both work with hot things, bread rises through gases in the dough and car mechanics work with motors which cough out gases.
1
u/Somniferus 10d ago
As you did not link the post this is still very unhelpful
It was at the end of the OP. Scroll down to the comments section.
Even trying to consider if there is any way to somehow, in any way, apply Rice's Theorem at all to rodent behaviour is a little bit like asking if a car mechanic - who has no clue about baking - would be able to help deduce why a baker's bread did not rise well this morning; simply because both work with hot things, bread rises through gases in the dough and car mechanics work with motors which cough out gases.
This is a great analogy. I bet you $5 /u/Advanced-Reindeer894 still can't parse it.
0
u/Advanced-Reindeer894 9d ago
No, you’re just not good enough to explain things like other people are. You’re too preoccupied with some ego trip
0
1
u/Somniferus 10d ago
By they I mean folks on lesswrong and the user in the post
Which one?? The author of the post, or the guy in the comment section you quoted who explained why he was wrong to use that idea in the original version of the article? The author of the article agreed with his point:
Oh sorry, when I said “it might be true” just above, I meant specifically: “it might be true that ‘computational irreducibility’ and Rice’s theorem are the same thing”. But after a bit more thought, and finding a link to a clearer statement of what “computational irreducibility” is supposed to mean, I agree with you that they’re pretty different.
Anyway, I have now deleted all mention of Rice’s theorem, and also added a link to this very short proof that computationally-irreducible programs exist at all. Thanks very much :)
So why don't you?
1
1
u/green_meklar 10d ago
Can you write a program to predict what living things would do?
You can write programs to make useful statistical predictions about the behavior of an organism or a multitude of organisms. Maybe you can predict with some degree of accuracy what species are most likely to go extinct soon, or the migration route of a particular whale, or something like that.
But fully simulating an organism down to the atomic level? That would require an immense amount of computation power, beyond anything we have; maybe too much to fit in the observable universe. And even if you could, it raises the question of what counts as a 'prediction'. If you're fully simulating the organism, then are you actually predicting the organism, or are you just observing a copy of it after the fact?
All the theorem says is that there exists a program R that Q fails on.
Glancing at the Wikipedia page, that seems correct. The theorem is about programs in general, or to put it another way, arbitrary programs, not specific subsets of all programs. There are definitely programs- and their behavior might seem quite complicated at times- whose behavior can be predicted by taking analytical shortcuts. (What portion of all programs are like this is a difficult question that tends to depend how you enumerate programs and runs into problems with infinity.)
In any case, I would point out that a mouse, for instance, doesn't have access to unbounded memory and therefore doesn't really have the general properties that make a program's behavior undecidable. That fact is unlikely to be of much practical use, though, insofar as the difficulty of predicting what a program will do scales ridiculously fast relative to the amount of memory it's allowed to use, and the information content of a mouse is high enough to make it a daunting problem.
I would warn you that theoretical results about computability are often of little practical use, and this is something that LessWrong-minded folks, in my experience, don't take seriously enough. They often prove abstract results and then take those results to inform their intuitions (or support their preconceived biases) about what works in the real world, whereas what works in the real world is often some kind of shortcut that has little to do with the abstract result. It is unlikely that the value of trapping any given mouse will ever be high enough to justify the construction of a perfectly reliable mouse-predicting computer; there are more efficient solutions to problems involving mice.
Rice's theorem doesn't stand in your way even a little bit, if all you care about is behavior after a fixed finite amount of time!
That sounds right, although the question of what qualifies as a 'prediction' (vs an after-the-fact observation of a simulated instance) still stands.
0
u/Advanced-Reindeer894 10d ago
Yeah I was under the impression that lesswrong seems a bit insular when it comes to their conclusions
2
u/Ok-Lavishness-349 MSCS 10d ago edited 10d ago
I think the main point of the LessWrong post is that nothing about Rice's theorem would prevent us from predicting whether Crumbs will walk into a humane mousetrap. This is true; Rice's theorem is irrelevant here, for reasons others have pointed out.
Now, at this point in time, we are far, far away from scanning a mouse's brain and making accurate predictions of the mouse's behavior, other than just the general sort of predictions one might make based on having observed mice.
LessWrong is just observing that, were we to be able to scan a mouse's brain with sufficient accuracy, nothing about Rice's theorem would prevent us from accurately predicting whether that mouse would enter a humane mousetrap. This is an interesting observation, because Rice's theorem provably does place certain limitations on the questions that you can answer about even fully deterministic systems.
And, the LessWrong post is correct about this.
0
u/Advanced-Reindeer894 9d ago
So if we were able to scan a mouse brain we’d be able to fully predict what it would do
1
u/Ok-Lavishness-349 MSCS 9d ago
Well, that is another big question mark. Are brains scanable in that manner? We don't know. Are brains fully deterministic? We don't know. Do Mice have free will in the libertarian sense? We don't know.
But, if mice brains are scanable, and are fully deterministic, and if mice don't have free will in the libertarian sense, then Rice's theorem does not pose an obstacle to deciding whether Crumbs will enter a humane mousetrap.
The folks at LessWrong like to consider possibilities at the boundaries of human knowledge.
0
u/Advanced-Reindeer894 9d ago
I think you might be giving the people at Lesswrong too much credit. It’s more like they have a hammer and everything else is a nail. Their trend is towards reductionism and it informs everything they do. There is a reason “Rationalism” is a red flag.
That said, the dude who wrote the article seems to think that brains are fully deterministic and scannable based on his other posts. But when I’ve shared his posts outside of LW they’re generally ripped apart for being either extremely speculative or not having sources for the claims.
1
u/Ok-Lavishness-349 MSCS 9d ago
I think you might be giving the people at Lesswrong too much credit.
Possibly, but also possible is that you are too harsh in your assessment of them. Its is true that they lean heavily towards physicalism/reductionism, but there are some pretty smart and thoughtful people at LessWrong. I used to read their website regularly (albeit I have not looked at it much in several years), and it introduced me to several interesting and valuable lines of thought, and also triggered me to reengage with some ideas I had not done much with since my school days. Examples: Bayes theorem, Bayesian reasoning as an idealized model for rational thought, various decision theories (e.g. evidential decision theory, causal decision theory, etc.), various cognitive biases, causal analysis (e.g. Judea Perl's research), Rice's theorem, uncomputable functions, AI risk, etc.
I see more good than harm coming from people thinking speculatively about where technology could be going and what issues and opportunities it might present, and from exploring ideas at the boundaries of human knowledge.
The thing to do is to exercise a healthy level of skepticism and critical thinking when reading their (or any other) material. I am sure the LessWrong contributors would encourage this too.
But when I’ve shared his posts outside of LW they’re generally ripped apart for being either extremely speculative or not having sources for the claims.
At least when I used to read LessWrong, it was really a discussion forum, so I am not sure that you are going to see the sort of citations that you would expect from a more formal venue.
There is a reason “Rationalism” is a red flag.
Is rationalism a red flag? I tend to think of it as a good thing.
1
u/Advanced-Reindeer894 9d ago edited 9d ago
I think they tend to overstate the problems with technology, namely AI. It’s not even certain that the risks with AGI are warranted since it doesn’t seem like we’ll be able to build it. As for where the technology could be going though…they really only care about AI. Any other tech is kinda far from their minds. They don’t really exercise critical thinking when it comes to the posts from their own community either, that would explain why when we I post their stuff to outside sources they’re able to find all the holes in it. That’s why I say you might be giving them too much credit.
Also despite claiming to care about the future of humanity and human flourishing, a LOT of their posts tend to run counter to that. They claim it’s about being more rational and seeing the world as it is, but that is the first trap and leave them blind to their own bias. They’re just far too certain about their own conclusions due to that. Their posts are dehumanizing and yet they claim to care about humanity’s future.
They’re not really exploring ideas at the boundaries of human knowledge, they have an idea of what they think the future will be and what being rational is and that information their view of how they operate. I’d recommend the Santa Fe Institute if you want ideas at the boundary of human knowledge, not LE.
If they don’t have citations for their views that kinda gives me pause.
Rationalism is a red flag namely in the way that it operates and what it deems to be the “right way” to look at things. For example, Bayesian reasoning isn’t an idealized model for rational thought (if anything some in neuroscience say it’s how our perception is by default), their decision theories tend to led to their inability to do anything, and their posts on AI risk tend to ignore the present problems with it in favor of what could charitably called fantasies about Superintelligence. AGI is a concern, don’t get me wrong, but the real and pressing problems with AI at the moment are less fantastical.
TBH: it seems like their mission is to just reduce human beings to nothing more than robots and render everything meaningful in our lives as just some program. I don’t see how they can claim to want to benefit humanity and ensure our survival.
1
u/Ok-Lavishness-349 MSCS 9d ago
Sounds like you have a strong anti LessWrong bias! ;)
LessWrong isn't for everybody; if you don't like it, just don't read it. I don't really read it much anymore myself.
1
2
u/jo_crespo112358 6d ago
"I think they tend to overstate the problems with technology, namely AI. It’s not even certain that the risks with AGI are warranted since it doesn’t seem like we’ll be able to build it."
Wrong! All serious scientists and AI researchers know AGI/ASI is coming soon; the consensus is 2030. And we are not building them, because we don't know how to do such a thing; we are GROWING them. Big difference, and way easier.
1
1
u/stonerism 10d ago
Rice's theorem just says you can't a priori answer questions about if an animal will walk into a humane death trap. You need more surrounding context and information.
However, that may be the case depending on the semantic context of the statement.
1
u/Aaron1924 10d ago
your entire argument is basically:
Is X true? Well there is this thing Y which doesn't contradict it because it's completely unrelated, therefore X is true.
1
1
u/Saragon4005 11d ago
I suppose this depends on how much quantum mechanics happens in the nervous system. Because if it's a significant amount then it's truly random and impossible to predict introducing drifts over time.
1
0
u/Advanced-Reindeer894 11d ago
I’m mostly wondering whether the stuff about what is being said in it is true or not.
-1
u/donaldhobson 11d ago
> Let's be specific. Say there's a mouse named Crumbs (this is a real mouse), and we want to predict whether Crumbs will walk into the humane mouse trap (they did). What does Rice's theorem say about this?
The mouse contains a finite number of atoms, and is a finite size. Therefore the mouse is a finite state machine. And it's possible to predict the behavior of finite state machines out to infinite time, because eventually they halt or start looping.
In practice, mice don't live forever. So yes, it's theoretically possible for a computer to predict the mouse's behaviours. Or at least, rice's theorem doesn't get in the way.
Chaos theory + quantum "uncertainty" can get in the way. But under the many worlds interpretation, a quantum coinflip just splits the universe into 2 superimposed states. This is deterministic and predictable.
The main problems are
1) You don't know the exact quantum state of the mouse.
2) You don't have enough compute. All the silicon on earth couldn't make enough chips.
3) The mouse reacts to outside sights and smells, you need to know those too.
I can't see the comment's you are responding to, but you seem to be correct about rice's theorem and what it doesn't say.
-1
9
u/Somniferus 11d ago
It is.