On 16 May 1997 I came to Belfast on my first official visit outside London as Prime Minister and made a speech here. I said then that it was no accident that I had chosen Northern Ireland for my first visit. I had come because I wanted to explain why I was committed to Northern Ireland and to the people here. I am told I have visited Northern Ireland more than any Prime Minister before me in five years of office. I have given this part of the UK as much energy and commitment as any other, because I value it as part of the UK which it will remain so long as a majority of people here wish to be part of it.

It is now four and a half years since the Belfast Agreement. Let us re-cap for a moment on the scale of what we agreed to do in April 1998. After 30 years of troubles, thousands of deaths, Northern Ireland part of the UK but governed unlike any other part of the UK, its communities divided, its daily life scarred in innumerable ways by sectarian bitterness; after all this, we agreed to shape a new future. Enemies would become not just partners in progress but sit together in Government. People who used to advocate the murder of British Ministers and security services, would be working with them. The police, the criminal justice system, the entire apparatus of Government would be reformed beyond recognition. People would put all the intransigence and hatred of the past behind them and co-operate. Britain and Ireland would reach a new relationship. The North and South of the island of Ireland would have a new set of institutions to mark change and co-operation within a wider framework of relationships within these islands. Paramilitaries who used to murder each other as a matter of routine would talk to each other and learn to live with each other. One of the most abnormal parts of the continent of Europe, never mind the UK, would become normal.

Did anyone seriously believe it would be easy? Did we seriously entertain the notion that the Agreement would be signed on the 10th April 1998 and on the 11th it would all be different?

It was a brave undertaking and a vast one. Even now I think that only in the first flush of a new Government could we have contemplated it.

And almost immediately the problems began. Prisoner release was there in black and white in the Agreement. But who could not understand the anguish of the families of the victims of terrorism when they saw their dearest ones' murderers given a rapturous welcome as they were released? Or those who were prepared to die in the cause of a united Ireland who saw their representatives take their place in a partitionist Assembly? Or as the changes bit in the policing of Northern Ireland, as the RUC gave way to the PSNI, who could not sympathise with the feelings of the former officers and their widows who felt they were stigmatised when all they did was to stand up for law and order against the perpetrators of organised violence? Or as the dissident republicans started their campaign to disrupt the process by a return to the bomb and bullet, who could not imagine the anger of those republicans working for peace, when the security measures of the British Government appeared to bear down on them, who supported the process, not on those who detested it?

All the time, of course, the malignant whisperings of those opposed to the process, always pointing out its faults, never aiding its strengths; and the evil violence from dissidents, from so-called loyalists, designed to re-ignite sectarian hatred to convulse such progress as we have made. At every step, those working for peace, trying to make the Agreement function, were being undermined, often from within their own community.

And, then, there were those who held the middle ground during the dark days of the Troubles, who provided much of the vision under-pinning the Agreement, only to see all the attention apparently given to the others as we tried to address the problems holding up the implementation of the Agreement. I know especially how frustrating this has been for the SDLP whose leadership has often felt its very reasonableness meant they counted for less. They should know this Agreement would never have happened without them. At crucial points too the Alliance helped it survive.

And then there were others like the Women's Coalition - decent, intelligent people that you often wished had power in the same proportion as their sense.

I watched it all, participated in the crises, made what I could of what I had before me. It has been four and a half years of hassle, frustration and messy compromise. After the dawn of the Agreement itself, there have been no moments of dazzling light when the decisions are plain, the good and the bad illuminated with crystal certainty, the path clear, the clarion call easy to sound. Each step has been a struggle. Each bit of advance ground out.

Indeed each negotiation in each office or stately home, accompanied by each ritual press conference, has often been groundhog day, for you, for me, for all of us.

As I said, I have spent more time on Northern Ireland, had more meetings, made more calls than any Prime Minister since 1922. I have lost count of the number of people who have shaken their heads at me and quoted Churchill's remark about "the dreary steeples of Fermanagh and Tyrone".

But let me state this with passion. I have not regretted for one second the effort or the hassle or the compromise. Because along with all of that, anyone can see there has also been progress.

Yes, there is still violence, but at a far, far reduced rate - in 1972, 470 people died. This year, so far, ten. Ten too many, but let us recognise the progress made.

The transformation in the economy has been enormous: unemployment at its lowest since 1975; long-term unemployment, down 65 per cent since the Agreement; manufacturing up 15 per cent, uniquely in the UK.

New jobs, new investment and a new way of life, as anyone who walks through Belfast city centre, or that of Derry or any other town can see.

And in all sorts of small but immensely symbolic ways life has changed. Not for all, I know. If you're in the Short Strand, or the victim of the latest pipe bomb attack or caught in the inter-community violence in North Belfast, these words about progress seem hollow. But actually the majority of people in Northern Ireland aren't mired in it. I remember in the 1980s coming to lecture in Northern Ireland with a colleague at the Bar. I remember how we couldn't go to a pub but had to go to a secure club. I remember how our hosts - accountants, I think - looked under their cars each morning. I remember at the airport being told about a terrorist incident a short distance away. I remember feeling when I was going there, I was going somewhere not just unsafe, but fundamentally different from any other part of the UK. Troops everywhere. Violence hanging over us as a cloud.

Northern Ireland is different today. Different and better.

But not as it should and can be.

The disappointment comes not from the modesty of our achievements, which are considerable; but from the enormity of our expectations.

And all the way through, there has been one fundamental issue and I want to state it as I see it. I don't want on this occasion to be diplomatic. I think I have the duty and a right, from the very time I have spent on this issue, to give you my frank view.

For years nationalist Ireland felt treated as second-class citizens. Let me cross out the word "felt". They were treated as second-class citizens. Let us not even assign blame. But let us not deny fact. They wanted to be part of a united Ireland. They regarded the whole concept of Northern Ireland as a sectarian construct. They believed the only way to secure justice was to secure unification.

Unionism at the time was supreme but it was also suspicious. Suspicious that if it gave way to the demands of nationalism, it was a slippery slope leading to a united Ireland. Suspicious that the British Government, of whatever colour, might say they were with them, but in reality would sell them out.

Today's Conservative Opposition attack us over the Belfast Agreement, calling us unprincipled, betraying Unionism. But I recall yesterday's Conservative Government, and Mrs Thatcher's Anglo-Irish Agreement and later Mr Major's Downing Street Declaration and the secret talks with the IRA even as the bombs exploded. But Unionism recalls it all too. And it leads to suspicion and also to insecurity.

Insecure for all the reasons just given. Insecure because they believed they had as much right to be unionists as the nationalists had to be nationalist, but that the world sided with the nationalists. Insecure because the more they demonstrated the overt signs of their Britishness, the more different from the rest of the UK they seemed.

And then into all this came the final and deadly ingredient of terrorism. I remember every year as a schoolboy spending my holidays in Ireland. Then one year, it all stopped.

It is hard for anyone to understand terrorism; and I do not believe it was ever or could ever be justified. But let us just reflect on its purposes. The purpose of republican terrorism was to create such a situation of chaos that Britain would give up on Northern Ireland. The purpose of loyalist terrorism was to retaliate, to dominate or to clear out Catholics.

For our part, the purpose of the British security response, often harsh, was to eliminate the violence as was our duty to do.

The fact is none of us succeeded in our purpose. The IRA were never going to bomb their way to a united Ireland and never could do so. I know the British people. They would simply never yield to it. The loyalists could not stand in the way of change. The British couldn't eliminate the IRA militarily.

But one hangover from this history remains. Even when republicans realised they were not going to get Britain to give up Northern Ireland by terror, they still thought it had another tactical purpose. It gave them negotiating leverage. The British wouldn't give up Northern Ireland by terror but they might be forced by terror to negotiate, to take Northern Ireland seriously, to take the claims of nationalism seriously.

The prospect of a ceasefire was a sufficiently tantalising prospect, to make the British pay attention and to get real movement from unionism.

At the core of the Agreement was this deal: in return for equality and justice - in politics, policing, in acceptance of nationalist identity - all parties were to commit exclusively to peace. And for unionism, the right of the people of Northern Ireland to remain part of the UK so long as a majority want to, was enshrined. Indeed, provided, in effect, unionists agreed to equality and to recognising the legitimacy of the identity of nationalists, the union would remain.

Of course, in working out the details, there were innumerable disputes over what equality, nationalist identity, the principle of consent meant in practice. This was one source of constant argument and disagreement, with the UK and Irish governments trying to negotiate a way through.

However, as time went on, it wasn't the main source. Increasingly, a different problem arose, and it is this that is at the heart of the present crisis.

Once the Agreement was signed, republicans committed themselves to peace. But they had their suspicions too. They believed that if they relinquished entirely the paramilitary, they might find the new British enthusiasm for the political suddenly waned; that they could and would be safely ignored again.

So the game began. Negotiation after negotiation, a decommissioning act here, an IRA statement there, progress made but slowly. However, it all came with another price. The unionists, unsurprisingly, kept pointing out that the IRA still existed; that this was not an organisation committed to exclusively peaceful means; and that they, the unionists, were obliged to sit in Government with its political wing.

So, rather than change being easier for unionists to embrace, and the British Government to drive through, change became a trade: with the IRA, to get more movement over leaving violence behind; with the unionists to compensate them for their discomfort at the IRA's continuing existence. The result? A belief on both sides that the other is not sincere and the British Government can't be trusted.

All the while, we were coming to a crunch point. Would republicanism really take the final step of committing exclusively, Sinn Fein and the IRA, to the peaceful path; or would they wait for the British finally to complete the normalisation of Northern Ireland, the policing and other changes promised, before doing so?

That is the crunch and the problem is that the very thing republicans used to think gave them negotiating leverage, doesn't do it anymore. It no longer acts to remove Unionist intransigence, but to sustain it; it no longer pushes the British Government forward, but delays us. It doesn't any longer justify David Trimble's engagement; it thwarts it.

I used to say we had to be sure all sides wanted the Agreement to work. I am sure everyone does. Unionism, certainly as represented by David Trimble, does. I believe that. They know the past has to be laid to rest. In any event, even if some don't, the British Government will simply not countenance any path other than implementing the Agreement. I also believe that Gerry Adams and Martin McGuinness want the Agreement to work. I think they have taken huge risks to try to bury the past. That is not a fond hope. That is my considered judgement after four and a half years of the closest working with them.

But the crunch is the crunch. There is no parallel track left. The fork in the road has finally come. Whatever guarantees we need to give that we will implement the Agreement, we will. Whatever commitment to the end we all want to see, of a normalised Northern Ireland, I will make. But we cannot carry on with the IRA half in, half out of this process. Not just because it isn't right any more. It won't work anymore.

Remove the threat of violence and the peace process is on an unstoppable path. That threat, no matter how damped down, is no longer reinforcing the political, it is actually destroying it. In fact, the continuing existence of the IRA as an active paramilitary organisation is now the best card those whom republicans call "rejectionist" unionists, have in their hand. It totally justifies their refusal to share power; it embarrasses moderate unionism and pushes wavering unionists into the hands of those who would just return Northern Ireland to the past. And because it also embarrasses the British and Irish Governments, it makes it harder for us to respond to nationalist concerns.

To this blunt question: "how come the Irish Government won't allow Sinn Fein to be in Government in the south until the IRA ceases its activity, but unionists must have them in Government in the North?", there are many sophisticated answers. But no answer as simple, telling and direct as the question.

So: that's where we are. Not another impasse. But a fundamental choice of direction, a turning point.

Why do I remain optimistic? Because underneath the surface, despite all the disputes, confrontations, anger and recrimination, there has been another benefit of the past few years. There has been a maturing, steady but probably unnoticed and unnoticeable by the majority of people, of the politics of Northern Ireland. Suspension has been bitterly opposed. But no-one wants to walk away.

There is a logic and reason compelling people towards finding a way through rather than using the crisis as an excuse to turn back. For republicans there is one very simple thing moving them in the direction of progress. Leave aside the disagreement over aspects of policing. They want to join. But the concept of republicans on the policing board, of young republicans becoming police officers, while maintaining an active paramilitary organisation, outside of the law, only needs to be stated, to be seen as an absurdity. There can't be two police forces. And as the changes in criminal justice take effect, how can there seriously be calls on the one hand for human rights and on the other, the savage beatings of people without any trial or due process without any rights, human or otherwise.

Any thinking republican can see this. That is not to understate the difficulties when, for many, this has been a way of life in republican communities often outside of the reach of the law. But there's no future in it and actually republicans know it.

In a different way, but with the same logic, the unionist community knows the only way of having a lasting peace is to have a just one. I have watched it change over these years. Just as coming into a partitionist Assembly and Executive was a huge leap for republicans, so each step of this process has meant huge pain for unionism. But in truth they are reconciled to the change, however painful, if they really believe that peace means peace. People say unionists now reject the Agreement. I don't think that's true. It's not that they don't support the concept of it. They don't believe it is being implemented properly whilst paramilitary activity remains.

And there's another change in unionism. They have been as unsettled as any by loyalist violence over the summer months. There has been a thought amongst some in the nationalist community that somehow unionists disregard, even secretly tolerate, loyalist paramilitaries. I know this not to be so. They now look upon this violence also as evidence of the Agreement not working. The vast majority of them have no residual sympathy with it at all.

When I met the new Chief Constable, Hugh Orde, I said this to him. For many years and for understandable reasons, the Police in Northern Ireland divided crime in two distinct categories: "ordinary" crime and paramilitary crime. When interface community violence happened, the police were never sure whether to police it or negotiate their way round it.

I said to him: how he polices it is up to him, but as far as the politics is concerned, I thought people in Northern Ireland were fed up - nationalists and unionists - with paramilitary violence being treated differently from "ordinary" crime. They wanted the same rules applied to them as apply to the decent law-abiding majority. I would point out that in addition to recent arrests of republicans, there have been now over 60 so-called loyalists arrested by the police. And not a single party I have seen in the last week has objected to it or urged caution.

I feel sorry for some of the political leaders of loyalism. They have tried hard and been immensely brave at critical points. But the activities of loyalist paramilitaries no longer fool anyone. There was always something bizarre about the idea of "loyalists" to the UK behaving in a way that was completely repugnant to 99% of the people in the UK they were supposed to be loyal to. But now most people do not see even a veneer of politics associated with the violence; and much of it has long since descended into gangsterism, drug-dealing and organised crime. However, I know the political leadership still want to find a way to lead loyalist communities back to political influence. They too need the help that comes from change.

So: what do we have? We have a situation where, in truth, the overwhelming majority of people in Northern Ireland and their political leaders want to see the Agreement implemented; want the institutions up and running again; accept the basic deal of justice for peace; but don't have the requisite trust to continue unless all the remaining bits of the puzzle are clear and fitted together.

Another inch by inch negotiation won't work. Symbolic gestures, important in their time, no longer build trust.

It's time for acts of completion. We will do our best to carry on implementing the Agreement in any event. But, should real change occur, we can implement the rest of the Agreement, including on normalisation, in its entirety and not in stages but together. And we are prepared to do what is necessary to protect the institutions against arbitrary interruption and interference. But that means also commitment from others. Unionism to make the institutions secure and stable. Nationalists to act if violence returns. Republicans to make the commitment to exclusively peaceful means, real, total and permanent. For all of us: an end to tolerance of paramilitary activity in any form. A decision that from here on in, a criminal act is a criminal act. One law for all, applied equally to all.

What has been interesting over the past few days has been not the comments of the politicians which, and I include ourselves, have been predictable; but the comments of people in the street. They have been genuinely sad that the Executive and local decision-making has been suspended; genuinely understanding of why; and very clear that the only way forward is for the changes to be completed, not rolled back.

And, as ever, ordinary people who work by instinct and who change naturally in their views, are ahead of politics which too often works by reference to established tradition and hallowed positions that survive the passage of time and sentiment, and make change, even when obvious, hard to acknowledge. The time in which we live, has two characteristics amongst others that are common in the civilised world. Especially post 11 September, there is a complete hatred of terrorism. No democratic political process can yield to it. That's why, quite apart from anything else, the violence in Northern Ireland is pointless. It is just an obstruction to politics. And the second thing is a complete intolerance of injustice on the basis of race or sex or religion. That's not to say such injustice doesn't exist. It does. But it has no place in respectable politics. It's regarded as unacceptable. And that is in fact true today in Northern Ireland in a way it wasn't 30 years ago. People may worry about loss of cultural identity but they know the days of justifying discrimination are gone.

In the end, justice for peace is in tune with our age. That's why this process in Northern Ireland despite it all, can still work.

Four and a half years on, the way forward remains the same. The question is: do we have the courage as politicians to do what the people want us to do? Do we trust each other enough to make the acts of completion happen? I can only tell you as British Prime Minister that I have that trust in all the parties I have worked with.

Now is the moment of choice. The same standards must apply to all. And we must implement the Agreement in full, because it is the choice of the people; the people here, the people in the South and the people of the United Kingdom as a whole.