Thinking on the Web

THINKING ON THE WEB

Berners-Lee, Godel, and Turing ¨

H. PETER ALESSO and CRAIG F. SMITH

A JOHN WILEY & SONS, INC., PUBLICATION

THINKING ON THE WEB

THINKING ON THE WEB

Berners-Lee, Godel, and Turing ¨

H. PETER ALESSO and CRAIG F. SMITH

A JOHN WILEY & SONS, INC., PUBLICATION

Copyright © 2006 by John Wiley & Sons, Inc. All rights reserved

Published by John Wiley & Sons, Inc., Hoboken, New Jersey

Published simultaneously in Canada.

No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any

form or by any means, electronic, mechanical, photocopying, recording, scanning, or otherwise,

except as permitted under Section 107 or 108 of the 1976 United States Copyright Act, without

either the prior written permission of the Publisher, or authorization through payment of the

appropriate per-copy fee to the Copyright Clearance Center, Inc., 222 Rosewood Drive, Danvers,

MA 01923, (978) 750-8400, fax (978) 750-4470, or on the web at www.copyright.com. Requests

to the Publisher for permission should be addressed to the Permissions Department, John Wiley &

Sons, Inc., 111 River Street, Hoboken, NJ 07030, (201) 748-6011, fax (201) 748-6008, or online at

http://www.wiley.com/go/permission.

Limit of Liability/Disclaimer of Warranty: While the publisher and author have used their best

efforts in preparing this book, they make no representations or warranties with respect to the

accuracy or completeness of the contents of this book and specifically disclaim any implied

warranties of merchantability or fitness for a particular purpose. No warranty may be created or

extended by sales representatives or written sales materials. The advice and strategies contained

herein may not be suitable for your situation. You should consult with a professional where

appropriate. Neither the publisher nor author shall be liable for any loss of profit or any other

commercial damages, including but not limited to special, incidental, consequential, or other

damages.

For general information on our other products and services or for technical support, please contact

our Customer Care Department within the United States at (800) 762-2974, outside the United

States at (317) 572-3993 or fax (317) 572-4002.

Wiley also publishes its books in a variety of electronic formats. Some content that appears in print

may not be available in electronic formats. For more information about Wiley products, visit our

web site at www.wiley.com.

Library of Congress Cataloging-in-Publication Data:

Alesso, H. P.

Thinking on the Web : Berners-Lee, Godel, and Turing / by H. Peter Alesso, Craig F. Smith. ¨

p. cm.

“A Wiley-Interscience publication.”

Includes bibliographical references and index.

ISBN-13: 978-0-471-76814-2

ISBN-10: 0-471-76814-6

1. World Wide Web. 2. Artificial intelligence. 3. Semantic Web. I. Smith, C. F.

(Craig Forsythe), 1950- II. Title.

TK5105.888.A3755 2006

004.67

8–dc22

2006041614

Printed in the United States of America

10 9 8 7 6 5 4 3 2 1

To: Chris and Kathy

CONTENTS

Foreword xiii

Preface xv

Acknowledgments xxi

Who This Book Is For xxiii

The Organization of This Book xxv

Associated Resources xxvii

PART I WHAT IS WEB INTELLIGENCE? 1

1 Empowering the Information Age 3

Overview 3

Thinking and Intelligent Web Applications 4

The Information Age 6

The World Wide Web 11

Limitations of Today’s Web 13

The Next Generation Web 14

Why Intelligent Ubiquitous Devices Improve Productivity 14

Conclusion 15

Exercises 16

Interlude #1: Thinking about Thinking 18

vii

viii CONTENTS

2 Godel: What is Decidable? 21 ¨

Overview 21

Philosophical and Mathematical Logic 22

Kurt Godel 26 ¨

Knowledge Representation 32

Computational Logic 34

Artificial Intelligence 35

Web Architecture and Business Logic 36

The Semantic Web 37

Conclusion 40

Exercises 41

Interlude #2: Truth and Beauty 43

3 Turing: What is Machine Intelligence? 45

Overview 45

What is Machine Intelligence? 45

Alan Turing 46

Turing Test and the Loebner Prize 48

John Searle’s Chinese Room 49

Artificial Intelligence 49

Machine Intelligence 50

Semantic Networks and Frames 51

Reasoning with Semantic Networks 51

Computational Complexity 52

Description Logic 54

Ontology 55

Inference Engines 55

Software Agents 56

Adaptive Software 56

Limitations and Capabilities 57

Conclusion 57

Exercises 58

Interlude #3: Computing Machines 60

4 Berners-Lee: What is Solvable on the Web? 63

Overview 63

The World Wide Web 64

Tim Berners-Lee 64

The Semantic Web Roadmap 68

Logic on the Semantic Web 75

Conclusion 77

CONTENTS ix

Exercises 77

Interlude #4: Turing’s Test 79

PART II WEB ONTOLOGY AND LOGIC 81

5 Resource Description Framework 83

Overview 83

HTML Language 84

XML Language 84

RDF Language 86

Basic Elements 89

RDF Schema 95

XQuery: XML Query Language 100

Conclusion 102

Exercises 102

Interlude #5: The Chinese Room 104

6 Web Ontology Language 107

Overview 107

Ontology Language 108

Ontology Language Requirements 109

Compatibility of OWL and RDF/RDFS 109

The OWL Language 111

Basic Elements 112

OWL Example: Compute Ontology 117

Ontology Example: Birthplace 118

Applying OWL 120

OWL Capabilities and Limitations 120

Conclusion 121

Exercises 121

Interlude #6: Machines and Brains 123

7 Ontology Engineering 125

Overview 125

Ontology Engineering 125

Constructing Ontology 127

Ontology Development Tools 128

Ontology “Spot” Example 128

Ontology Methods 131

x CONTENTS

Ontology Sharing and Merging 132

Ontology Libraries 133

Ontology Matching 133

Ontology Mapping 135

Ontology Mapping Tools 135

Conclusion 136

Exercises 136

Interlude #7: Machines and Meaning 138

8 Logic, Rules, and Inference 143

Overview 143

Logic and Inference 144

Monotonic and Nonmonotonic Rules 147

Descriptive Logic 148

Inference Engines 149

RDF Inference Engine 152

Conclusion 155

Exercises 155

Interlude #8: Machines and Rules 157

9 Semantic Web Rule Language 161

Overview 161

Rule Systems 161

Rule Languages 162

Semantic Web Rule Language 163

Conclusion 164

Exercise 165

Interlude #9: Machines and Language 166

10 Semantic Web Applications 169

Overview 169

Semantic Web Applications 169

Semantic Web Services 171

Semantic Search 171

e-Learning 172

Semantic Bioinformatics 173

Enterprise Application Integration 173

Knowledge Base 175

Conclusion 175

Exercise 176

Interlude #10: Distributed Intelligence 177

CONTENTS xi

11 Web Ontology Language for Services 179

Overview 179

XML-based Web Services 180

Next Generation Web Services 180

Creating an OWL-S Ontology for Web Services 190

Conclusion 190

Exercises 190

Interlude #11: The Semantic Web 191

12 Semantic Search Technology 193

Overview 193

Search Engines 193

Semantic Search 196

Semantic Search Technology 197

Web Search Agents 199

Semantic Methods 201

Latent Semantic Index Search 201

TAP 203

Swoogle 204

Conclusion 206

Exercises 206

Interlude #12: The Halting Problem 207

13 Semantic Patterns and Adaptive Software 209

Overview 209

Patterns in Software Design 209

Pattern Frame 210

Semantic Patterns 211

Self-Organizing and Adaptive Software 213

Conclusion 214

Exercise 214

Interlude #13: The Semantic Web and Rules 215

14 Semantic Tools 217

Overview 217

Semantic Tools 217

Semantic Web Services Tools 221

Conclusion 224

Exercise 224

Interlude #14: The Semantic Web and Language 225

xii CONTENTS

15 Challenges and Opportunities 227

Overview 227

Semantic Doubts 228

Semantic Opportunities 229

The Challenges 229

Balancing Proprietary and Open Standards 231

Conclusion 232

Interlude #15: The Semantic Web and Zeno’s Paradox 234

Bibliography 235

Glossary 243

Acronyms 257

Index 259