The halting problem for Turing machines is decidable on a set of asymptotic probability one. The proof is sensitive to the particular computational models.

We study the parameterized complexity of the problem to decide whether a given natural number n satisfies a given $\Delta _0$ -formula $\varphi (x)$ ; the parameter is the size of $\varphi $. This parameterization focusses attention on instances where n is large compared to the size of $\varphi $. We show unconditionally that this problem does not belong to the parameterized analogue of $\mathsf {AC}^0$. From this we derive that certain natural upper bounds on the complexity of (...) our parameterized problem imply certain separations of classical complexity classes. This connection is obtained via an analysis of a parameterized halting problem. Some of these upper bounds follow assuming that $I\Delta _0$ proves the MRDP theorem in a certain weak sense. (shrink)

The open-domain Frame Problem is the problem of determining what features of an open task environment need to be updated following an action. Here we prove that the open-domain Frame Problem is equivalent to the Halting Problem and is therefore undecidable. We discuss two other open-domain problems closely related to the Frame Problem, the system identification problem and the symbol-grounding problem, and show that they are similarly undecidable. We then reformulate the Frame (...) Problem as a quantum decision problem, and show that it is undecidable by any finite quantum computer. (shrink)

The uniform halting problem (UH) can be stated as follows.Give a decision procedure which for any given Turing machine (TM) will decide whether or not it has an immortal instantaneous description (ID).An ID is called immortal if it has no terminal successor. As it is generally the case in the literature (see e.g. Minsky [3, p. 118]) we assume that in an ID the tape must be blank except for some finite numbers of squares. If we remove this (...) restriction the UH becomes the immortality problem (IP). The UH should not be confused with the initialised uniform halting problem (whether or not a TM has an immortal ID when started in a specified state) which can easily be shown to be undecidable (see e.g. Minsky [3, p. 151]). (shrink)

We present an abstract framework in which we give simple proofs for Gödel’s First and Second Incompleteness Theorems and obtain, as consequences, Davis’, Chaitin’s and Kritchman-Raz’s Theorems.

We describe a proof by a computer program of the unsolvability of the halting problem. The halting problem is posed in a constructive, formal language. The computational paradigm formalized is Pure LISP, not Turing machines. The machine was led to the proof by the authors, who suggested certain function definitions and stated certain intermediate lemmas. The machine checked that every suggested definition was admissible and the machine proved the main theorem and every lemma. We believe this (...) is the first instance of a machine checking that a given problem is not solvable by machine. (shrink)

The uniform halting problem (UH) can be stated as follows:Give a decision procedure which for any given Turing machine (TM) will decide whether or not it has an immortal instantaneous description (ID).An ID is called immortal if it has no terminal successor. As it is generally the case in the literature (see e.g. Minsky [4, p. 118]) we assume that in an ID the tape must be blank except for some finite number of squares. If we remove this (...) restriction the UH becomes the immortality problem (IP). (shrink)

Complexity is pleased to announce the installment of Prof Hiroki Sayama as its new Chief Editor. In this Editorial, Prof Sayama describes his feelings about his recent appointment, discusses some of the journal’s journey and relevance to current issues, and shares his vision and aspirations for its future.

The question of when to stop an unsuccessful experiment can be difficult to answer from an individual perspective. To help to guide these decisions, we turn to the social epistemology of science and investigate knowledge inquisition within a group. We focused on the expensive and lengthy experiments in high energy physics, which were suitable for citation-based analysis because of the relatively quick and reliable consensus about the importance of results in the field. In particular, we tested whether the time spent (...) on a scientific project correlates with the project output. Our results are based on data from the high energy physics laboratory Fermilab. They point out that there is an epistemic saturation point in experimenting, after which the likelihood of obtaining major results drops. With time the number of less significant publications does increase, but highly cited ones do not get published. Since many projects continue to run after the epistemic saturation point, it becomes clearer that decisions made about continuing them are not always rational. (shrink)

Our limited a priori-reasoning skills open a gap between our finding a proposition conceivable and its metaphysical possibility. A prominent strategy for closing this gap is the postulation of ideal conceivers, who suffer from no such limitations. In this paper I argue that, under many, maybe all, plausible unpackings of the notion of ideal conceiver, it is false that ideal negative conceivability entails possibility.

Recourse to meta-argument is an important feature of successful argument exchanges; it is where norms are made explicit or clarified, corrections are offered, and inferences are evaluated, among much else. Sadly, it is often an avenue for abuse, as the very virtues of meta-argument are turned against it. The question as to how to manage such abuses is a vexing one. Erik Krabbe proposed that one be levied a fine in cases of inappropriate meta-argumentative bids (2003). In a recent publication (...) (2022) Beth Innocenti expands on this notion of a penalty, arguing that some meta-arguments should be halted with “shouting, cussing, sarcasm, name-calling.” In this essay, we review Innocenti’s case that these confrontations and haltings improve the argumentative circumstances. We provide three reasons that this promise is not well-founded. First, that such confrontations have a significant audience problem, in that they are more likely to be interpreted as destroying the argumentative context than improving it. Second, that Innocenti’s procedural justification, that those who lose meta-discussions should pay a penalty, is not satisfied if the meta-discussion is halted. And third, there is a boundary problem for the cases, since it seems there is no principled reason to restrict halting meta-arguments just to these cases (especially if there is no meta-discussion on the matter to make the bounds explicit). Though expressions of anger can be appropriate in argument, we argue, it cannot take the place of argument. (shrink)

We argue that while the new opposition in Azerbaijan between 2005 and 2013 did not realize all the goals set, it influenced a new generation of young activists who became the loudest supporters of democratic and secular values in Azerbaijan. This grassroots activation of the youth brought noticeable changes to some parts of Azerbaijani society by questioning the authority of traditional values. Many young people, especially students found a platform to discuss their problems concerning everyday basic issues such as intimate (...) relationships as well as their freedom to live in accordance with their personal choices and desires without the family interference in the light of theoretical questions such as the importance of liberal democratic values, individual liberties, and the rule of law. The successfully established connections between material problems and transcendental ideals encouraged some young people to participate in the open discussions and seminars organized by the new opposition. Because of the emergence of this new generation of active youth, the government was forced to incorporate some elements of this new discourse at least by making some cosmetic changes within its structures. The government became successful in its attempts of weakening the new opposition by hijacking its ideas and creating similar but pro-government organizations; neutralizing or buying some well-known opposition figures such as writers and journalists; and finally, persecuting the leading members of the youth organizations. (shrink)

Problem of truth and reality is age old in the field of philosophy as well as in the field of science. People very often confuse between ‘Truth’ and ‘Reality’ Most people think them to be one and the same, but there are differences. Whatever exist is real, reality and existence are interchangeable words. We can say truth, which is unchangeable and reality, which exist but change. False, which is not exist at all. People have suggested various taste to decide (...) the truth falsity of our description of reality. Some suggested Pragmatic theory and some other have suggested Coherence as a test of truth. Realism is also an ontological theory and has been probably the most ancient one. According to ancient man, real is that which perceived. Latter on, due to religious impact the knower became more important then the knowing object. Barkeley developed an extreme position that the objective material world does not exist at all. Dewey has developed the position called Instrumentalism. Halt, Perry, Marvin, Pitkin are the chief advocates of this position. Philosophers such as Darke, Lovejoy, Cellars, and Santayana held a position of Critical Realism. These people hold that mind does not see the object directly as they are but only through their representatives, as regards the object of knowledge is concerned, the Neo Realist are monist while Critical Realist are dualist. Indian rationalist philosopher Dr. D.D. Bandiste introduces a new concept of reality Radical Realism. He proved that knowledge change the knower not the object. to him every new knowledge make some change or other inthe knowing person. Epistemological position of john Dewey called instrumentalism. According to him knowledge is an instrument of action and a meaningful action is always of a problem-solving type. Every knowledge is an instrument to serve some need or other, neither is any knowledge final, nor is any truth final. Not only everything in the world is changing, their mutual relations also change. Knowledge is not a goal, but only a instrument to achieve this or that goal. In my paper I haves discussed various theories regarding whether knowledge change the object known. In this contest I have discussed varieties of realism, Idealismand so on, but importantly I have also discussed a new theory Radical Realism. (shrink)

This discussion paper describes the attempt of an imagined group of non-ecologists to determine the population growth rate from field data. The Modellers wrestle with the multiple definitions of the growth rate available in the literature and the fact that, in their modelling, it appears to be drastically model-dependent, which seems to throw into question the very concept itself. Specifically, they observe that six representative models used to capture the data produce growth-rate values, which differ significantly. Almost ready to concede (...) that the problem they set for themselves is ill-posed, they arrive at an alternative point of view that not only preserves the identity of the concept of the growth rate, but also helps discriminate between competing models for capturing the data. This is accomplished by assessing how robustly a given model is able to generate growth-rate values from randomized time-series data. This leads to the proposal of an iterative approach to ecological modelling in which the definition of theoretical concepts and model selection complement each other. The paper is based on high-quality field data of mites on apple trees and may be called a “data-driven opinion piece”. (shrink)

A pseudo-natural algorithm for the word problem of a finitely presented group is an algorithm which not only tells us whether or not a word w equals 1 in the group but also gives a derivation of 1 from w when w equals 1. In [13], [14] Madlener and Otto show that, if we measure complexity of a primitive recursive algorithm by its level in the Grzegorczyk hierarchy, there are groups in which a pseudo-natural algorithm is arbitrarily more complicated (...) than an algorithm which simply solves the word problem. In a given group the lowest degree of complexity that can be realised by a pseudo-natural algorithm is essentially the derivational complexity of that group. Thus the result separates the derivational complexity of the word problem of a finitely presented group from its intrinsic complexity. The proof given in [13] involves the construction of a finitely presented group G from a Turing machine T such that the intrinsic complexity of the word problem for G reflects the complexity of the halting problem of T, while the derivational complexity of the word problem for G reflects the runtime complexity of T. The proof of one of the crucial lemmas in [13] is only sketched, and part of the purpose of this paper is to give the full details of this proof. We will also obtain a variant of their proof, using modular machines rather than Turing machines. As for several other results, this simplifies the proofs considerably. MSC: 03D40, 20F10. (shrink)

In this paper we study generic complexity of undecidable problems. It turns out that some classical undecidable problems are, in fact, strongly undecidable, i.e., they are undecidable on every strongly generic subset of inputs. For instance, the classical Halting Problem is strongly undecidable. Moreover, we prove and analog of the Rice theorem for strongly undecidable problems, which provides plenty of examples of strongly undecidable problems. Then we show that there are natural super-undecidable problems. i.e., problem which are (...) undecidable on every generic (not only strongly generic) subset of inputs. In particular, there are finitely presented semigroups with super-undecidable word problem. To construct strongly- and super-undecidable problems we introducea method of generic amplification (an analog of the amplification in complexity theory). Finally, we construct absolutely undecidable problems, which stay undecidable on every non-negligible set of inputs. Their construction rests on generic immune sets. (shrink)

We give a new proof of the following result : it is undecidable whether a given calculus, that is a finite set of propositional formulas together with the rules of modus ponens and substitution, axiomatizes the classical logic. Moreover, we prove the same for every superintuitionistic calculus. As a corollary, it is undecidable whether a given calculus is consistent, whether it is superintuitionistic, whether two given calculi have the same theorems, whether a given formula is derivable in a given calculus. (...) The proof is by reduction from the undecidable halting problem for the so-called tag systems introduced by Post. We also give a historical survey of related results. (shrink)

Die Untersuchung besteht aus drei Teilen. Im ersten Teil argumentiere ich, daß in der frühen Neuzeit durch die Zurückweisung des scholastischen Vokabulars das Problem, Ordnung und Regelmäßigkeit in der Natur zu erklären, neu aufgeworfen wird. Descartes führt den Begriff des Naturgesetzes ein, um dieses Problem zu lösen. Im zweiten und dritten Teil analysiere ich, was Descartes unter einem Naturgesetz versteht. Im zweiten Teil zeige ich, daß es für die verbreitete Auffassung, Descartes halte Naturgesetze für ewige Wahrheiten, keine guten (...) Gründe gibt. Im dritten Teil untersuche ich die Rolle, die Gott – Descartes zufolge – als Urheber der Naturgesetze spielt. Ich argumentiere, daß die “Daumenkino”-Auffassung von Naturgesetzen keine Folge der “creatio continua”- These ist, sondern eine Konsequenz des Cartesischen Materiebegriffs. Schließlich bemühe ich mich verständlich zu machen, weshalb Descartes fürchtet, seine Naturgesetzauffassung lege die Hypothese nahe, Gott sei die Weltseele. (shrink)

A recent proposal to solve the halting problem with the quantum adiabatic algorithm is criticized and found wanting. Contrary to other physical hypercomputers, where one believes that a physical process “computes” a (recursive-theoretic) non-computable function simply because one believes the physical theory that presumably governs or describes such process, believing the theory (i.e., quantum mechanics) in the case of the quantum adiabatic “hypercomputer” is tantamount to acknowledging that the hypercomputer cannot perform its task.

The Busy Beaver Competition is held by Turing machines. The better ones halt taking much time or leaving many marks, when starting from a blank tape. In order to understand the behavior of some Turing machines that were once record holders in the five-state Busy Beaver Competition, we analyze their halting problem on all inputs. We prove that the halting problem for these machines amounts to a well-known problem of number theory, that of the behavior (...) of the repeated iteration of Collatz-like functions, that is functions defined by cases according to congruence classes. (shrink)

Accelerating Turing machines are Turing machines of a sort able to perform tasks that are commonly regarded as impossible for Turing machines. For example, they can determine whether or not the decimal representation of contains n consecutive 7s, for any n; solve the Turing-machine halting problem; and decide the predicate calculus. Are accelerating Turing machines, then, logically impossible devices? I argue that they are not. There are implications concerning the nature of effective procedures and the theoretical limits of (...) computability. Contrary to a recent paper by Bringsjord, Bello and Ferrucci, however, the concept of an accelerating Turing machine cannot be used to shove up Searle's Chinese room argument. (shrink)

Hypercomputation—the hypothesis that Turing-incomputable objects can be computed through infinitary means—is ineffective, as the unsolvability of the halting problem for Turing machines depends just on the absence of a definite value for some paradoxical construction; nature and quantity of computing resources are immaterial. The assumption that the halting problem is solved by oracles of higher Turing degree amounts just to postulation; infinite-time oracles are not actually solving paradoxes, but simply assigning them conventional values. Special values for (...) non-terminating processes are likewise irrelevant, since diagonalization can cover any amount of value assignments. This should not be construed as a restriction of computing power: Turing’s uncomputability is not a ‘barrier’ to be broken, but simply an effect of the expressive power of consistent programming systems. (shrink)

This paper takes up one of the least apparent problems of Philosophy. It believes that there are problems in philosophy as a discipline; especially in the field of Metaphysics. Problems of Body and Mind, Freewill and Determinism, Euthanasia and Sanctity of life, are such problems which have been given spectacular cognitions and ameliorative opinions. But problems in philosophy are not restrained to these ones. That is why the paper seeks to appraise the ‘Problem of Method’ as it occurs to (...) the universal frame of Philosophy. It also claims that the Existentialist approach can be a model that the philosophical traditions should follow in solving or evading the metaphilosophical problem. The above will be carried out by looking at what the word ‘method’ means, its affiliation with disciplines generally then with philosophy; emphasizing much on its problematic features as vivid in some philosophical quests. Furthermore, the notion of existentialism shall be explicated as the sublime, in putting to a halt the problematic trend of method in the whole enterprise of Philosophy. (shrink)

This article deals with the question of whether an increased teaching of business ethics can/will have a positive effect on the fight against corruption in companies. It is written from a (South) African perspective. Statistics about the alarming state of corruption in South African businesses are provided in the beginning. A Hegelian approach to the problem, in terms of which theory can and does influence practice, is compared to a Marxist approach, in terms of which theory is only a (...) reflection of practice. The author chooses a position that mediates between these two extremes. In the end, he develops a model that relies heavily on the idea of an ethics of responsibility that draws on Aristotle's idea of phronesis (practical wisdom based on deliberation). The practical implications of these ideas for the utilization of business ethics teaching in companies are consequently spelt out. While more teaching of this discipline cannot guarantee better morals in a company, it can better equip all involved to deal with the ever-increasing moral problems that business people have to deal with. S. Afr. J. Philos. Vol.22(2) 2003: 128–138. (shrink)

Wars are large-scale conflicts between organized groups of belligerents, which involve suffering, devastation, and brutality unlike almost anything else in human experience. Whatever one’s other beliefs about morality, all should agree that the horrors of war are all but unconscionable, and that warfare can be justified only if we have some compel- ling account of what is worth fighting for, which can justify contributing, as individu- als and as groups, to this calamitous endeavour. Although this question should obviously be central (...) to both philosophical and politi- cal discussion about war, it is at the forefront of neither. In recent years, philosophical discussion of warfare has bloomed, but the debate has focused on whom we may kill, on the assumption that our aims are justified.1 Political debate, meanwhile, is more concerned with matters of prudence, international law, and public justification, than with reassessing what is worth fighting for. For wars of intervention to halt or prevent massive humanitarian crises, this gap is not so troubling. When warfare is the only means to prevent the mass killing or enslavement of the innocent, the purposes of military force are clear enough (though undoubtedly many other problems remain). The problem is more pressing, how- ever, for the justification of national defence.3 Although common-sense morality and international law view national defence as the paradigm case of justified warfare, grounding this consensus is surprisingly difficult.4 We typically believe that any state is justified in using lethal force to protect its territory against any form of uninvited military incursion by any other state. And yet we lack a good argument to explain why this should be so. In this chapter, I explain why one familiar and otherwise plausible approach to the justification of killing in war cannot adequately ground common-sense views of permissible national defence.5 Reductionists believe that justified warfare reduces to an aggregation of acts that are justified under ordinary principles of interpersonal morality.6 The standard form of reductionism focuses on the principles governing killing in ordinary life, specifically those that justify intentional killing in self- and other-defence, and unintended but foreseen (for short, collateral) killing as a lesser evil. Justified warfare, on this view, is no more than the coextension of multiple acts justified under these two principles. Reductionism is the default philosophical approach to thinking through the ethics of killing in war. It makes perfect sense to ask what principles govern permissible kill- ing in general, before applying them to the particular context of war. If it cannot deliver a plausible set of conclusions about when national defence is permitted, then we must either revise our beliefs about which conclusions count as plausible, or else face the significant challenge of developing a different theoretical model for justifying war- fare—an exceptionalist model, which views war as an exception to the regular moral landscape, to which principles apply which apply to nothing else but war.7 We must show, in other words, that there is something worth fighting for in wars of national defence, which is not engaged when we use force in any other context. The chapter proceeds as follows. Section 2.2 sets out the argument against reduc- tionism.8 Section 2.3 considers and rebuts one common response to the argument, which has often been thought sufficient grounds to disregard its conclusion. Section 2.4 then asks whether a modified reductionism would survive unscathed by the argu- ment. Finally, section 2.5 sets out some desiderata on a plausible exceptionalist alterna- tive. Section 2.6 concludes. (shrink)

Let ϕ be a fixed numerical function. If the k-state Turing machine M with input string ϕ(k) (that is, started in its initial state scanning the leftmost 1 of a single string of ϕ(k) 1s on an otherwise blank tape) produces the output string m (that is, halts in its halting state scanning the leftmost 1 of a single string of m 1s on an otherwise blank tape), we shall say that the ϕ-fecundity of M is m. If M (...) halts in any other position or state, or fails to halt, its ϕ-fecundity is 0. (shrink)

Published in Vienna in 1936, _The Authoritarian State_ by Eric Voegelin has remained virtually unknown to the public until now. Sales of the German edition were halted following the Nazi invasion of Austria in 1938, and the entire printing was later destroyed by wartime bombing. In this volume, Voegelin offers a critical examination of the most prominent European theories of state and constitutional law of the period while providing a political and historical analysis of the Austrian situation. He discusses the (...) dismissal of Parliament in 1933, the civil war, the murder of Federal Chancellor Dollfuss, the adoption of the "Authoritarian Constitution" of 1934, and the predicament of being sandwiched between Hitler and Mussolini. A radical critique of Hans Kelsen's pure theory of law lies at the heart of this work, marking Voegelin's definitive departure from Neo-Kantian epistemology. For the first time, Voegelin elaborates on the important distinction between theoretical concepts and political symbols as a basis for explaining the nontheoretical and speculative character of ideologies, both left and right. He shows that _total_ and _authoritarian_ are symbols of ideological self-interpretation that have no theoretical value, a distinction basic to his later work in _The New Science of Politics._ Available for the first time in English, _The Authoritarian State_ is a valuable addition to the Voegelin canon and to the field of intellectual history in general. (shrink)

Farmers’ decisions to conserve natural resources generally and soil and water particularly are largely determined by their knowledge of the problems and perceived benefits of conservation. In Ethiopia, however, farmer perceptions of erosion problems and farmer conservation practices have received little analysis or use in conservation planning. This research examines farmers’ views of erosion problems and their conservation knowledge and practices in the Beressa watershed in the central highlands of Ethiopia. Data were obtained from a survey of 147 farm households (...) managing 713 fields during the 2002/2003 cropping season. In-depth interviews and group discussions were also held with the farmers to obtain additional information. The results show that 72% of the farmers reported erosion problems, and they recognized that conservation was necessary. However, they considered erosion to be severe mostly when visible signs – rills and gullies – appeared on their fields. The majority of the farmers believe that erosion could be halted, and they use a range of practices for erosion control and fertility improvement. These include contour plowing (83%), drainage ditches (82%), and stone terraces/bunds (73%). Nevertheless, despite decades of conservation intervention in the area, it appears that most farmers have developed negative attitudes towards externally recommended measures. The research concludes that under the conditions present in the Ethiopian central highlands, soil and water conservation interventions should consider farmers’ conservation knowledge and practices to improve acceptance and adoption of the recommendations. (shrink)

A novel solution is offered for how emotional experiences can function as sources of immediate prima facie justification for evaluative beliefs, and in such a way that suffices to halt a justificatory regress. Key to this solution is the recognition of two distinct kinds of emotional skill and how these must be working in tandem when emotional experience plays such a justificatory role. The paper has two main parts, the first negative and the second positive. The negative part criticises the (...) epistemic credentials of Epistemic Perceptualism Perceptual illusions. Philosophical and psychological essays, Palgrave Macmillan, Basingstoke, 2012; Tappolet in Emotions, value, and agency. Oxford University Press, Oxford, 2016; Döring in The Philos Quart 53: 214–230, 2003; Döring in Dialectica 61: 363–394, 2007; Elgin, in: Georg, Kunzle Epistemology and emotions, Ashgate Alderchot, Farnham, 2008; Roberts in Emotions: an essay in aid of moral psychology, Cambridge University Press, Cambridge, 2003), the view that emotional experience alone suffices to prima facie justify evaluative beliefs in a way that is analogous to how perceptual experience justifies our beliefs about the external world. The second part of the paper develops an account of emotional skill and uses this account to frame a revisionary form of Epistemic Perceptualism that succeeds where the traditional views could not. I conclude by considering some objections and replies. (shrink)

Recently, there has been an upsurge of attention focused on bias and its impact on specialized artificial intelligence applications. Allegations of racism and sexism have permeated the conversation as stories surface about search engines delivering job postings for well-paying technical jobs to men and not women, or providing arrest mugshots when keywords such as “black teenagers” are entered. Learning algorithms are evolving; they are often created from parsing through large datasets of online information while having truth labels bestowed on them (...) by crowd-sourced masses. These specialized AI algorithms have been liberated from the minds of researchers and startups, and released onto the public. Yet intelligent though they may be, these algorithms maintain some of the same biases that permeate society. They find patterns within datasets that reflect implicit biases and, in so doing, emphasize and reinforce these biases as global truth. This paper describes specific examples of how bias has infused itself into current AI and robotic systems, and how it may affect the future design of such systems. More specifically, we draw attention to how bias may affect the functioning of a robot peacekeeper, a self-driving car, and a medical robot. We conclude with an overview of measures that could be taken to mitigate or halt bias from permeating robotic technology. (shrink)

A novel solution is offered for how emotional experiences can function as sources of immediate prima facie justification for evaluative beliefs, and in such a way that suffices to halt a justificatory regress. Key to this solution is the recognition of two distinct kinds of emotional skill (what I call generative emotional skill and doxastic emotional skill) and how these must be working in tandem when emotional experience plays such a justificatory role. The paper has two main parts, the first (...) negative and the second positive. The negative part criticises the epistemic credentials of Epistemic Perceptualism (e.g., Tappolet 2012, 2016; Doring 2003, 2007; Elgin 2008; Roberts 2003), the view that emotional experience alone suffices to prima facie justify evaluative beliefs in a way that is analogous to how perceptual experience justifies our beliefs about the external world. The second part of the paper develops an account of emotional skill and uses this account to frame a revisionary form of Epistemic Perceptualism that succeeds where the traditional views could not. I conclude by considering some objections and replies. (shrink)

Farmers’ decisions to conserve natural resources generally and soil and water particularly are largely determined by their knowledge of the problems and perceived benefits of conservation. In Ethiopia, however, farmer perceptions of erosion problems and farmer conservation practices have received little analysis or use in conservation planning. This research examines farmers’ views of erosion problems and their conservation knowledge and practices in the Beressa watershed in the central highlands of Ethiopia. Data were obtained from a survey of 147 farm households (...) managing 713 fields during the 2002/2003 cropping season. In-depth interviews and group discussions were also held with the farmers to obtain additional information. The results show that 72% of the farmers reported erosion problems, and they recognized that conservation was necessary. However, they considered erosion to be severe mostly when visible signs – rills and gullies – appeared on their fields. The majority of the farmers believe that erosion could be halted, and they use a range of practices for erosion control and fertility improvement. These include contour plowing (83%), drainage ditches (82%), and stone terraces/bunds (73%). Nevertheless, despite decades of conservation intervention in the area, it appears that most farmers have developed negative attitudes towards externally recommended measures. The research concludes that under the conditions present in the Ethiopian central highlands, soil and water conservation interventions should consider farmers’ conservation knowledge and practices to improve acceptance and adoption of the recommendations. (shrink)

A set theory model of reality, representation and language based on the relation of completeness and incompleteness is explored. The problem of completeness of mathematics is linked to its counterpart in quantum mechanics. That model includes two Peano arithmetics or Turing machines independent of each other. The complex Hilbert space underlying quantum mechanics as the base of its mathematical formalism is interpreted as a generalization of Peano arithmetic: It is a doubled infinite set of doubled Peano arithmetics having a (...) remarkable symmetry to the axiom of choice. The quantity of information is interpreted as the number of elementary choices (bits). Quantum information is seen as the generalization of information to infinite sets or series. The equivalence of that model to a quantum computer is demonstrated. The condition for the Turing machines to be independent of each other is reduced to the state of Nash equilibrium between them. Two relative models of language as game in the sense of game theory and as ontology of metaphors (all mappings, which are not one-to-one, i.e. not representations of reality in a formal sense) are deduced. (shrink)

We explore the possibility of using quantum mechanical principles for hypercomputation through the consideration of a quantum algorithm for computing the Turing halting problem. The mathematical noncomputability is compensated by the measurability of the values of quantum observables and of the probability distributions for these values. Some previous no-go claims against quantum hypercomputation are then reviewed in the light of this new positive proposal.

All known structural extensions of the substructural logic $\textbf{FL}_{\textbf{e}}$, the Full Lambek calculus with exchange/commutativity (corresponding to subvarieties of commutative residuated lattices axiomatized by $\{\vee, \cdot, 1\}$ -equations), have decidable theoremhood; in particular all the ones defined by knotted axioms enjoy strong decidability properties (such as the finite embeddability property). We provide infinitely many such extensions that have undecidable theoremhood, by encoding machines with undecidable halting problem. An even bigger class of extensions is shown to have undecidable deducibility (...) problem (the corresponding varieties of residuated lattices have undecidable word problem); actually with very few exceptions, such as the knotted axioms and the other prespinal axioms, we prove that undecidability is ubiquitous. Known undecidability results for non-commutative extensions use an encoding that fails in the presence of commutativity, so and-branching counter machines are employed. Even these machines provide encodings that fail to capture proper extensions of commutativity, therefore we introduce a new variant that works on an exponential scale. The correctness of the encoding is established by employing the theory of residuated frames. (shrink)

"All the limitative Theorems of metamathematics and the theory of computation suggest that once the ability to represent your own structure has reached a certain critical point, that is the kiss of death: it guarantees that you can never represent yourself totally. Godel's Incompleteness Theorem, Church's Undecidability Theorem, Turing's Halting Problem, Turski's Truth Theorem -- all have the flavour of some ancient fairy tale which warns you that `To seek self-knowledge is to embark on a journey which...will always (...) be incomplete, cannot be charted on a map, will never halt, cannot be described. " - Douglas R. Hofstadter.. (shrink)

Die Ansicht, dass Leibniz urn 1700 oder einige Zeit danach ein überzeugter Idealist war oder wurde, der allein an die Realität der Geister und ihrer Ideen glaubte, hält sich merkwürdigerweise in der neueren Sekundärliteratur. In diesem Beitrag beurteilen wir die Textgrundlage für diese Behauptung nach von uns für solide gehaltenen Kriterien einer historischen Interpretation, wobei sich die Behauptung unserer Ansicht nach als unzureichend erweist. Obwohl Leibniz zur Überzeugung gelangt war, dass wirkliche "Atome" der Natur keine Ausdehnung hätten, war er sein (...) Leben hindurch auf die Geistesunabhängigkeit lebender Kreaturen festgelegt, in der Art, die eindeutig Idealismus ausschließt. Wir versuchen, die tieferen Gründe für die Beharrlichkeit der idealistischen Sichtweise, trotz ihrer textlichen und konzeptualen Schwierigkeiten, aufzudecken, indem wir sie letztlich in den ahistorischen Präferenzen der Kommentatoren lokalisieren. (shrink)

This book uses the friendly format of the computing language Prolog to teach a full formal predicate logic. With Prolog, the scope and limits of both logic and computing can be explored and experimented. Students learning formal logic in a Prolog format can begin using their already developed informal abilities in logic to program in Prolog and conversely learn enough formal logic to examine Prolog and computing in general so major fundamental theorems can be demonstrated. Cases such as Church's Thesis, (...) Church's Theorem, Turing's Halting Problem, and Godel's Incompleteness Theorem provide the author with the means to assess some of the philosophical implications of logic and computing. Henry designed the book for undergraduate students, but it is also useful for philosophers and theologians who wish to see how computer programming serves as a probe into philosophical matters. Contents: The Formalization of Logic; Propositional Logic; Predicate Logic; Prolog: Programming in Logic; Logic Machines; The Scope and Limits of Logic and Logic Machines; Philosophical Reflections; Appendix; Bibliography; Index. (shrink)

Numbers. Natural numbers -- Integers -- Real numbers -- Irrational and transcendental numbers -- Funny numbers. Zero -- e : the unnatural natural number -- [Phi] : the golden ratio -- i : the imaginary number -- Writing numbers. Roman numerals -- Egyptian fractions -- Continued fractions -- Logic. Mr. Spock is not logical -- Proofs, truth, and trees : oh my! -- Programming with logic -- Temporal reasoning -- Sets. Cantor's diagonalization : infinity isn't just infinity -- Axiomatic set (...) theory : keep the good, dump the bad -- Models : using sets as the LEGOs of the math world -- Transfinite numbers : counting and ordering infinite sets -- Group theory : finding symmetries with sets -- Mechanical math. Finite state machines : simplicity goes far -- The turing machine -- Pathology and the heart of computing -- Calculus : no, not that calculus- [lambda] calculus -- Numbers, booleans, and recursion -- Types, types, types : modeling [lambda] calculus -- The halting problem. (shrink)

It is a trivial fact that if we have a square table filled with numbers, we can always form a column which is not yet contained in the table. Despite its apparent triviality, this fact underlies the foundations of most of the path-breaking results of logic in the second half of the nineteenth and the first half of the twentieth century. We explain how this fact can be used to show that there are more sequences of natural numbers than there (...) are natural numbers, that there are more real numbers than natural numbers and that every set has more subsets than elements (all results due to Cantor); we indicate how this fact can be seen as underlying the celebrated Russell paradox; and we show how it can be employed to expose the most fundamental result of mathematical logic of the twentieth century, Gödel's incompleteness theorem. Finally, we show how this fact yields the unsolvability of the halting problem for Turing machines. (shrink)

Turing's World is a self-contained introduction to Turing machines, one of the fundamental notions of logic and computer science. The text and accompanying diskette allow the user to design, debug, and run sophisticated Turing machines in a graphical environment on the Macintosh. Turning's World introduces users to the key concpets in computability theory through a sequence of over 100 exercises and projects. Within minutes, users learn to build simple Turing machines using a convenient package of graphical functions. Exercises then progress (...) through a significant portion of elementary computability theory, covering such topics as the Halting problem, the Busy Beaver function, recursive functions, and undecidability. Version 3.0 is an extensive revision and enhancement of earlier releases of the program, allowing the construction of one-way and two-way finite state machines (finite automata), as well as nondeterministic Turing and finite-state machines. Special exercises allow users to explore these alternative machines. (shrink)