We consider computation in the presence of closed timelike curves (CTCs), as proposed by Deutsch. We focus on the case in which the CTCs carry classical bits (as opposed to qubits). Previously, Aaronson and Watrous showed that computation with polynomially many CTC bits is equivalent in power to PSPACE. On the other hand, Say and Yakaryilmaz showed that computation with just 1 classical CTC bit gives the power of "postselection", thereby upgrading classical randomized computation (BPP) to the complexity class BPP_path and standard quantum computation (BQP) to the complexity class PP. It is natural to ask whether increasing the number of CTC bits from 1 to 2 (or 3, 4, etc.) leads to increased computational power. We show that the answer is no: randomized computation with logarithmically many CTC bits (i.e., polynomially many CTC states) is equivalent to BPP_path. (Similarly, quantum computation augmented with logarithmically many classical CTC bits is equivalent to PP.) Spoilsports with no interest in time travel may view our results as concerning the robustness of the class BPP_path and the computational complexity of sampling from an implicitly defined Markov chain.

It is a widely believed, though unproven, conjecture that the capability of postselection increases the language recognition power of both probabilistic and quantum polynomial-time computers. It is also unknown whether polynomial-time quantum machine

It was recently proved that a sound and complete qualitative simulator does not exist, that is, as long as the input-output vocabulary of the state-of-the-art QSIM algorithm is used, there will always be input models which cause any simulator with a coverage guarantee to make spurious predictions in its output. In this paper, we examine whether a meaningfully expressive restriction of this vocabulary is possible so that one can build a simulator with both the soundness and completeness properties. We prove several negative results: All sound qualitative simulators, employing subsets of the QSIM representation which retain the operating region transition feature, and support at least the addition and constancy constraints, are shown to be inherently incomplete. Even when the simulations are restricted to run in a single operating region, a constraint vocabulary containing just the addition, constancy, derivative, and multiplication relations makes the construction of sound and complete qualitative simulators impossible.

This paper describes ALİ, the first computer program which can solve primary school-level arithmetic problems stated in Turkish. This task involves several subtasks: morphological analysis of every word in the input, syntactic analysis of each sentence, semantic analysis of words, providing a description of the commonsense world that is large enough to enable the correct answering of the problems, and generating the answer in human-readable form.

We present a technique for automatically determining certain pairs of qualitative simulation predictions to be mutually contradictory. This leads the simulator to produce more informative outputs, which results in improved performance in reasoning tasks like diagnosis, model revision, and deletion of spurious "timelines" containing the input state.

We have identified a source of spurious predictions inside the qualitative simulation algorithm QSIM. The algorithm fails to check for violations of l'Hopital's rule, which causes the addition of inconsistent states to the behavior tree. Our proposed solution involves adding a new state filter to make the required controls and does not necessitate any additions or restrictions in the input set. We make use of extended corresponding value tuples spanning multiple constraints. The necessary modifications to the algorithm are explained and the technique is demonstrated on examples. Used in conjunction with other spurious behavior elimination methods, this approach would increase QSIM's ability to handle more complex systems.

Postdiction is the task of finding the possible pasts of a physical system, given its model and current state. We present an appropriately modified version of Kuipers' QSIM algorithm to perform postdiction by reverse qualitative simulation. The necessary changes to the algorithm are explained and the closed world assumption is discussed in this new light. The new algorithm can be used for diagnostic purposes.

A source of spurious predictions inside the qualitative simulation algorithm QSIM proposed by B. Kuiper (1986) is identified. The proposed solution involves the use of interval corresponding values for filtering inconsistent states and does not require any additions or restrictions in the input set, unlike the other approaches to the spurious prediction elimination problem. The time and space complexities of the algorithm are not affected by the modification.>