We argue from the Church-Turing thesis (Kleene Mathematical logic. New York: Wiley 1967) that a program can be considered as equivalent to a formal language similar to predicate calculus where predicates can be taken as functions. We can relate such a calculus to Wittgenstein’s first major work, the Tractatus, and use the Tractatus and its theses as a model of the formal classical definition of a computer program. However, Wittgenstein found flaws in his initial great work and he explored these (...) flaws in a new thesis described in his second great work; the Philosophical Investigations. The question we address is “can computer science make the same leap?” We are proposing, because of the flaws identified by Wittgenstein, that computers will never have the possibility of natural communication with people unless they become active participants of human society. The essential difference between formal models used in computing and human communication is that formal models are based upon rational sets whereas people are not so restricted. We introduce irrational sets as a concept that requires the use of an abductive inference system. However, formal models are still considered central to our means of using hypotheses through deduction to make predictions about the world. These formal models are required to continually be updated in response to peoples’ changes in their way of seeing the world. We propose that one mechanism used to keep track of these changes is the Peircian abductive loop. (shrink)

The effective reasoning capability of an agent can be defined as its capability to infer, within a given space and time bound, facts that are logical consequences of its knowledge base. In this paper we show how to determine the effective reasoning capability of an agent with limited memory by encoding the agent as a transition system and automatically verifying whether a state where the agent believes a certain conclusion is reachable from the start state. We present experimental results using (...) the Model Based Planner (MBP) which illustrates how the length of the deduction varies for different memory sizes. (shrink)

There is a long history of cryptographic hash functions, i.e. functions mapping variable-length strings to fixed-length strings, and such functions are also expected to enjoy certain security properties. Hash functions can be effected via modular arithmetic, permutation-based schemes, chaotic mixing, and so on. Herein we introduce the notion of an artificial-life (ALife) hash function (ALHF), whereby the requisite mixing action of a good hash function is accomplished via ALife rules that give rise to complex evolution of a given system. Various (...) security tests have been run, and the results reported for examples of ALHFs. (shrink)

We have a variety of different ways of dividing up, classifying, mapping, sorting and listing the objects in reality. The theory of granular partitions presented here seeks to provide a general and unified basis for understanding such phenomena in formal terms that is more realistic than existing alternatives. Our theory has two orthogonal parts: the first is a theory of classification; it provides an account of partitions as cells and subcells; the second is a theory of reference or intentionality; it (...) provides an account of how cells and subcells relate to objects in reality. We define a notion of well-formedness for partitions, and we give an account of what it means for a partition to project onto objects in reality. We continue by classifying partitions along three axes: (a) in terms of the degree of correspondence between partition cells and objects in reality; (b) in terms of the degree to which a partition represents the mereological structure of the domain it is projected onto; and (c) in terms of the degree of completeness with which a partition represents this domain. (shrink)

The application of digital humanities techniques to philosophy is changing the way scholars approach the discipline. This paper seeks to open a discussion about the difficulties, methods, opportunities, and dangers of creating and utilizing a formal representation of the discipline of philosophy. We review our current project, the Indiana Philosophy Ontology (InPhO) project, which uses a combination of automated methods and expert feedback to create a dynamic computational ontology for the discipline of philosophy. We argue that our distributed, expert-based approach (...) to modeling the discipline carries substantial practical and philosophical benefits over alternatives. We also discuss challenges facing our project (and any other similar project) as well as the future directions for digital philosophy afforded by formal modeling. (shrink)

A sequence generator is a finite graph, more general than, but akin to, the usual state diagram associated with a finite automaton. The nodes of a sequence generator represent complete states, and each node is labeled with an input and an output state. An element of the behavior of a sequence generator is obtained by taking the input and output states along an infinite path of the graph.Sequence generators may be associated with formulas of the monadic predicate calculus, in which (...) the individual variables range over the times 0, 1, 2, 3, [middle dot][middle dot][middle dot], and the predicate variables represent complete states, input states, and output states. An unrestricted singulary recursion is a formula in which the complete state at time [tau] + 1 is expressed as a truth-function of the complete state at time [tau] and the input states from times [tau] + 1 to [tau] + h. Necessary and sufficient conditions are given for a formula derived from a sequence generator being equivalent to an unrestricted singulary recursion. (shrink)

Recent new paradigms of computation, based on biological and physical models, address in a radically new way questions of efficiency and challenge assumptions ...

Partial functions are ubiquitous in both mathematics and computer science. Therefore, it is imperative that the underlying logical formalism for a general-purpose mechanized mathematics system provide strong support for reasoning about partial functions. Unfortunately, the common logical formalisms — first-order logic, type theory, and set theory — are usually only adequate for reasoning about partial functionsin theory. However, the approach to partial functions traditionally employed by mathematicians is quite adequatein practice. This paper shows how the traditional approach to partial functions (...) can be formalized in a range of formalisms that includes first-order logic, simple type theory, and Von-Neumann—Bernays—Gödel set theory. It argues that these new formalisms allow one to directly reason about partial functions; are based on natural, well-understood, familiar principles; and can be effectively implemented in mechanized mathematics systems. (shrink)

Over the past decade, teaching and learning in virtual worlds has been at the forefront of many higher education institutions around the world. The DEHub Virtual Worlds Working Group (VWWG) consisting of Australian and New Zealand higher education academics was formed in 2009. These educators are investigating the role that virtual worlds play in the future of education and actively changing the direction of their own teaching practice and curricula. 47 academics reporting on 28 Australian higher education institutions present an (...) overview of how they have changed directions through the effective use of virtual worlds for diverse teaching and learning activities such as business scenarios and virtual excursions, role-play simulations, experimentation and language development. The case studies offer insights into the ways in which institutions are continuing to change directions in their teaching to meet changing demands for innovative teaching, learning and research in virtual worlds. This paper highlights the ways in which the authors are using virtual worlds to create opportunities for rich, immersive and authentic activities that would be difficult or not possible to achieve through more traditional approaches. (shrink)

Medical expert systems (MES) are knowledge-based computer programs that are designed for advising physicians on diagnostical and therapeutical decision-making. They use heuristic methods developed by Artificial Intelligence researchers in order to retrieve from large knowledge-bases information needed in the situation. Constructing the knowledge-base of a MES embraces the problem of explicating and fixing the conceptual, causal and epistemic relations between a lot of medical objects. There is a number of preconditions which any adequate representation of such knowledge must fulfil, among (...) them the conditions of consistency, of completeness, of unequivocality, etc. Existing systems for classification and coding, like ICD and SNOMED, are not designed for the needs of constructing expert systems or, more generally, of knowledge processing and knowledge engineering. Their syntax is not sufficiently rich for expressing the more complex structures of (medical) knowledge. What is needed, is a language that can be used for expressing logical and descriptive relations between medical objects and facts, approximately at the level of the language of second order predicate logic. Simultaneously, it must be possible to process this language at the machine level. This can be achieved by using some dialects of the programming language LISP or, particularly, by using the programming language PROLOG. Thus, in order to achieve a suitable classification system, it is necessary to develop a system of medical data structures and predicates expressed in LISP or PROLOG. (shrink)

This is a copy of the presentation given at the Workshop on Agency and Distributed Cognition at Macquarie University, March 2012.

This paper reports on an ongoing ARC Discovery Project that is conducting design research into learning in collaborative virtual worlds (CVW).The paper will describe three design components of the project: (a) pedagogical design, (b)technical and graphics design, and (c) learning research design. The perspectives of each design team will be discussed and how the three teams worked together to produce the CVW. The development of productive failure learning activities for the CVW will be discussed and there will be an interactive (...) demonstration of the project's CVW. (shrink)

Agents need to be able to change their beliefs; in particular, they should be able to contract or remove a certain belief in order to restore consistency to their set of beliefs, and revise their beliefs by incorporating a new belief which may be inconsistent with their previous beliefs. An influential theory of belief change proposed by Alchourron, G¨ardenfors and Makinson (AGM) [1] describes postulates which a rational belief revision and contraction operations should satisfy. The AGM postulates have been perceived (...) as characterising idealised rational reasoners, and the corresponding belief change operations are considered unsuitable for implementable agents due to their high computational cost [3]. The main result of this paper is showing that an efficient (linear time) belief contraction operation nevertheless satisfies all but one of the AGM postulates for contraction. This contraction operation is defined for a realistic rule-based agent which can be seen as a reasoner in a very weak logic; although the agent’s beliefs are deductively closed with respect to this logic, checking consistency and tracing dependencies between beliefs is not computationally expensive. Finally, we give a non-standard definition of belief revision in terms of contraction for our agent. (shrink)

The somewhat old-fashioned concept of philosophical categories is revived and put to work in automated ontology building. We describe a project harvesting knowledge from Wikipedia’s category network in which the principled ontological structure of Cyc was leveraged to furnish an extra layer of accuracy-checking over and above more usual corrections which draw on automated measures of semantic relatedness.

Practical reasoners are resource-bounded—in particular they require time to derive consequences of their knowledge. Building on the Timed Reasoning Logics (TRL) framework introduced in [1], we show how to represent the time required by an agent to reach a given conclusion. TRL allows us to model the kinds of rule application and conflict resolution strategies commonly found in rule-based agents, and we show how the choice of strategy can influence the information an agent can take into account when making decisions (...) at a particular point in time. We prove general completeness and decidability results for TRL, and analyse the impact of communication in an example system consisting of two agents which use different conflict resolution strategies. (shrink)

Integration of ontologies begins with establishing mappings between their concept entries. We map categories from the largest manually-built ontology, Cyc, onto Wikipedia articles describing corresponding concepts. Our method draws both on Wikipedia’s rich but chaotic hyperlink structure and Cyc’s carefully defined taxonomic and common-sense knowledge. On 9,333 manual alignments by one person, we achieve an F-measure of 90%; on 100 alignments by six human subjects the average agreement of the method with the subject is close to their agreement with each (...) other. We cover 62.8% of Cyc categories relating to common-sense knowledge and discuss what further information might be added to Cyc given this substantial new alignment. (shrink)

Wikipedia is a goldmine of information; not just for its many readers, but also for the growing community of researchers who recognize it as a resource of exceptional scale and utility. It represents a vast investment of manual effort and judgment: a huge, constantly evolving tapestry of concepts and relations that is being applied to a host of tasks. This article provides a comprehensive description of this work. It focuses on research that extracts and makes use of the concepts, relations, (...) facts and descriptions found in Wikipedia, and organizes the work into four broad categories: applying Wikipedia to natural language processing; using it to facilitate information retrieval and information extraction; and as a resource for ontology building. The article addresses how Wikipedia is being used as is, how it is being improved and adapted, and how it is being combined with other structures to create entirely new resources. We identify the research groups and individuals involved, and how their work has developed in the last few years. We provide a comprehensive list of the open-source software they have produced. (shrink)

Driven by concrete applications, Algorithm Engineering complements theory by the benefits of experimentation and puts equal emphasis on all aspects arising during a cyclic solution process ranging from realistic modeling, design, analysis, ...

Abstract State Machines (ASMs) provide a formal method for transparent design and specification of complex dynamic systems. They combine advantages of informal and formal methods. Applications of this method motivate a number of computability and decidability problems connected to ASMs. Such problems result for example from the area of verifying properties of ASMs. Their high expressive power leads rather directly to undecidability respectively uncomputability results for most interesting problems in the case of unrestricted ASMs. Consequently, it is rather natural to (...) ask whether there exist expressive classes of ASMs for which we can prove positive decidability and computability results. In this work, we introduce such a class of ASMs. The concept is similar to the one of the guarded fragment of first-order logic. We analyze the expressive power of this class and prove that it is stronger than Datalog LITE and the guarded fragment of first-order fixed point logic. Some decidability and computability results have been proven in earlier works. (shrink)

This paper presents the intelligent virtual animals that inhabit Omosa, a virtual learning environment to help secondary school students learn how to conduct scientific inquiry and gain concepts from biology. Omosa supports multiple agents, including animals, plants, and human hunters, which live in groups of varying sizes and in a predator-prey relationship with other agent types (species). In this paper we present our generic agent architecture and the algorithms that drive all animals. We concentrate on two of our animals to (...) present how different parameter values affect their movements and inter/intra-group interactions. Two evaluations studies are included: one to demonstrate the effect of different components of our architecture; another to provide domain expert validation of the animal behavior. (shrink)

In order to achieve genuine web intelligence, building some kind of large general machine-readable conceptual scheme (i.e. ontology) seems inescapable. Yet the past 20 years have shown that manual ontology-building is not practicable. The recent explosion of free user-supplied knowledge on the Web has led to great strides in automatic ontology building, but quality-control is still a major issue. Ideally one should automatically build onto an already intelligent base. We suggest that the long-running Cyc project is able to assist here. (...) We describe methods used to add 35K new concepts mined from Wikipedia to collections in ResearchCyc entirely automatically. Evaluation with 22 human subjects shows high precision both for the new concepts’ categorization, and their assignment as individuals or collections. Most importantly we show how Cyc itself can be leveraged for ontological quality control by ‘feeding’ it assertions one by one, enabling it to reject those that contradict its other knowledge. (shrink)

Images in Computer Science: Clarifications Required. The Age of the Images Images take a rather prominent place in contemporary life in the western ...

In addition, this book contains tools that, in principle, can search a set of algorithms to see whether a problem is solvable, or more specifically, if it can be solved by an algorithm whose computations are efficient.

We present a minimum message length (MML) framework for trajectory partitioning by point selection, and use it to automatically select the tolerance parameter ε for Douglas-Peucker partitioning, adapting to local trajectory complexity. By examining a range of ε for synthetic and real trajectories, it is easy to see that the best ε does vary by trajectory, and that the MML encoding makes sensible choices and is robust against Gaussian noise. We use it to explore the identification of micro-activities within a (...) longer trajectory. This MML metric is comparable to the TRACLUS metric – and shares the constraint of abstracting only by omission of points – but is a true lossless encoding. Such encoding has several theoretical advantages – particularly with very small segments (high frame rates) – but actual performance interacts strongly with the search algorithm. Both differ from unconstrained piecewise linear approximations, including other MML formulations. (shrink)