To be on the road with a new prime minister on his first big international adventure is to observe him before the habits and resentments set in. Things are always more interesting when they are still a little provisional, rough-edged and buzzing with new enthusiasm. This week we saw Gordon Brown feeling his way into the job, taking his band across the Atlantic to try and break America.It suits him. I think he is beginning to clock how much more appealing he is as a new boy than a know-all. One of the lessons he says he has learned in the past few weeks is that things happen, events come and go, you have to keep your focus on the fundamentals. Not quite que sera, sera, but as close as this PM will ever get to it.
It was remarkable that, on his very first visit to the back of the plane to chat to the hacks as prime minister, Brown chose to bring the foreign secretary with him. It is only a few months since David Miliband was being urged to run for the leadership. Now the PM treats him like a brilliant protege. Old Gordon would never have been sufficiently comfortable to share the limelight on such an occasion. "He is completely bloody unrecognisable," said one long-time aide, mopping his brow in mock relief. This is spin, of course. But it is not just spin.
The Darfur resolution was the most glittering souvenir in the prime ministerial knapsack as we headed back home. But the less-noticed strategic prize was persuading George Bush to say so much about "ideology": the shorthand used by the president for what Brown calls the "battle for hearts and minds" in the struggle against terrorism. His staff are not yet happy with this slogan - too vague, too resonant of Vietnam - but it captures something more than the usual bromides about "shared values" and the need to be nice to people. Bush was most nervous about what Brown would say on Iraq. But the PM kept drawing the president back to the need to engage in a cultural, intellectual and counter-insurgency programme of the kind that was fought against Soviet communism.
Brown's own thinking has shifted on this matter, and the turning point was the alleged involvement of doctors in the car bomb plot. In the past he has tended to believe that the root cause of global terrorism was economic deprivation. The inferno at Glasgow airport sealed in his mind a shift of analysis: that twisted ideas, rather than poverty, were the true basis of the problem. In the PM's eyes, it follows that the next phase of the struggle must be more subtle, much of it completely concealed.
In this he has recently been inspired by a 1999 book on the CIA and the cultural cold war, Who Paid the Piper? by the British journalist Frances Stonor Saunders. He was particularly intrigued by the CIA's management of the Boston Symphony Orchestra as "the juggernaut of American culture". Brown cites the success of the anti-communist Congress for Cultural Freedom in harnessing the intellectual firepower of a generation of authors and artists, and funding journals such as Encounter, Transition and Partisan Review.
Does this mean that MI5 will now be spending millions on anti-Islamist magazines and that the London Symphony Orchestra is going to be dispatched to the Middle East with bugs in their cellos? Not quite. But it does mean finding resources for moderate Muslims and cutting off funding to anyone else: Brown believes that the old left's version of "multiculturalism" led us to the insanity of financing groups precisely because they were extreme. Expect big changes.
He has also been impressed by the work of David Kilcullen, a former Australian army officer and academic anthropologist who now works for the US state department. Kilcullen's core belief is that the war on terror is better described as a "global counter-insurgency". He refers to the "information battlefield" but insists that the west's strategy must be radically localised: each region, each village, needs a different counter-terrorist tactic.
The Brown camp agrees that the propaganda campaigns adopted by Bush's long-time ally Karen Hughes, the US under-secretary for public diplomacy and public affairs, have been much too centralised and old-fashioned. The Kilcullen doctrine on winning "hearts and minds" is based not on making local people feel affection for you, but on persuading them that you can protect them better than the enemy.
Meanwhile, young Muslims drawn to the flames of Islamism - in West Yorkshire as much as Basra - have to be targeted for "ideological conversion", a process Kilcullen compares to the tactics used to keep young men out of street gangs. Easier said than done, of course. But this is the way Brown's counter-terrorist thinking is heading: away from invasions, "crusades", and "shock and awe", and towards something that owes much more to a cold war theorist such as George Kennan than it does to Donald Rumsfeld or, indeed, to Tony Blair.
Brown is right to be using this time to think deeply and experimentally, for he will never enjoy such freedom again. The honeymoon will end, the mood will harden, the Tories will regroup and renew their attack. The road ahead will often be rocky. But, in the motorcade speeding down Second Avenue towards the airport, one could only reflect that this PM's greatest triumph to date has been to persuade the world that he is not an exhausted traveller, limping and grey after 10 years in office, but a man at the very start of a journey.
Matthew d'Ancona, the editor of the Spectator; a longer version of this article appears in today's issue of the magazine.