Sure but the AI wouldn't necessarily have to respond. I think the main flaw in the Turing test is it's cultural dependence. I would argue that Eliza has passed plenty of Turing tests, mostly with people who had a chance encounter with it.

But why would an AGI individual have to be able to lie about it's childhood ? It could simply have a childhood. But I understand your argument : "Human" AI is constantly trained for the function "be a human". Machine intelligence is being trained with "is human X cheating", "is this spam", "what is the french for apple", "which way will stock X go" (and other "what will <large number of humans> do in situation X" questions) ... functions.

Keep in mind that your own brain is also simply running an algorithm, with "hidden state". Here's the first thing it hides pretty well : there's no single "you", there's about 300 regions in your brain, that are physically different, in different locations, and not directly linked. And if the rest of your brain gets disabled, each of those 300 regions can use your body to convince your own mother it's really you she's talking to. And the function your brain is executing is not to "have a soul" or something like that, but is mostly a behaviour-copy algorithm. It searches out other humans, observes their actions, learns to predict them and then uses what it's learned to "be you". Most people will not believe this is how it works, not even when they know quite a bit about neurons, and know pretty well that this is what our neurons do.

But when it comes right down to it, you, me, everyone is an "AI algorithm" just like Google search. Aside from the shear scale, number of connections mostly, there is nothing all that remarkable about the hardware it's running on.

I love how an AGI algorithm is presented in the follow up to the Battlestar Galactica series, "Caprica". Zoe Graystone explains it at one point in the series. It's fiction of course, but still. Her algorithm searches the internet, your computer, and everything and anything it can find for pictures and videos of it's "target" and then builds the function "given situation X, what would <human> do ?" and then puts the algorithm in a virtual body that looks like the human, and uploads it to V-world. She runs it on herself, a friend and accidentally on a third person she doesn't know and then proceeds to get herself blown up by a friend/terrorist (they can be both at the same time, you know) in the first episode, and their avatars wake up in V-world, sort of a facebook virtual reality edition, unaware of what has happened (and as V-world is mostly used for sex, dancing and debauchery it's not that easy to find out unless you're looking for it). Currently we don't have nearly enough data on any person to make this work ... but I am pretty convinced it is possible to make this work.

This would work, since it's doing the same thing your brain does when it hears the question "do you remember feeling happy when your mother held you when you were a baby ?". First, your brain doesn't actually remember that either way. It simply works it's way through to a good answer to that question. The thing it'll do is predict how you should answer that question, given (mostly) how other humans answer that question.

This is a very different problem from "lying about its childhood", specifically it's much more solvable. Can I predict how humans would answer questions about their childhood ? Certainly. Easy. Make the algorithm take enough contextual information into account (so that it both realizes what realistic answers are and either answers realistically or responds in a way that humans respond when they don't have a "good prediction" for an answer, for instance by saying they don't remember, or by changing the subject, or ...)

If you have young kids you will see this process in action. You have to "teach" kids memory. When they talk only a little, if you ask them something about earlier that day, they will respond. And the response makes sense, but it's not actually what happened. You will at some point realise this and correct them. Correcting them teaches them to match up what happened with their response, because they learn to predict that that's what's expected of people. Over time this correcting them will work, and they will have learned memory (and then they learn to lie, especially on questions like "did you hit your sister ?", and when that ends badly they learn to "not lie", like adults do. "Did you hit your sister ?" "She stole my lego").

Note that the underlying memory is also a prediction. If I ask you what happened this morning, and you want to try to answer correctly, you will start with an obvious fact (which isn't necessarily the truth), like "I woke up". Your brain will take that thought, and predict (not remember) what happened next. So I woke up, ok next, brushing teeth, ok next, read cell phone messages, ok next, ... ah ! the answer to the question.