Search results for "Turing machine"

Ultrametric Algorithms and Automata

2015

We introduce a notion of ultrametric automata and Turing machines using p-adic numbers to describe random branching of the process of computation. These automata have properties similar to the properties of probabilistic automata but complexity of probabilistic automata and complexity of ultrametric automata can differ very much.

How to simulate free will in a computational device

1999

Since we believe that human brain is not a purely deterministic device merely reacting to the environment but rather it is capable to a free will, Theoretical Computer Science has also tried to develop a system of notions generalizing determinism. Nondeterministic and probabilistic algorithms were the first generalizations. Nondeterministic machines constitute an important part of the Theory of Computation. Nondeterminism is a useful way to describe possible choices. In real life there are many regulations restricting our behavior. These regulations nearly always leave some freedom for us how to react. Such regulations are best described in terms of nondeterministic algorithms. Nondetermini…

Quantum Real - Time Turing Machine

2001

The principles of quantum computation differ from the principles of classical computation very much. Quantum analogues to the basic constructions of the classical computation theory, such as Turing machine or finite 1-way and 2-ways automata, do not generalize deterministic ones. Their capabilities are incomparable. The aim of this paper is to introduce a quantum counterpart for real - time Turing machine. The recognition of a special kind of language, that can't be recognized by a deterministic real - time Turing machine, is shown.

Space-Efficient 1.5-Way Quantum Turing Machine

2001

1.5QTM is a sort of QTM (Quantum Turing Machine) where the head cannot move left (it can stay where it is and move right). For computations is used other - work tape. In this paper will be studied possibilities to economize work tape space more than the same deterministic Turing Machine can do (for some of the languages). As an example language (0i1i|i ≥ 0) is chosen, and is proved that this language could be recognized by deterministic Turing machine using log(i) cells on work tape , and 1.5QTM can recognize it using constant cells quantity.

On computation in the limit by non-deterministic Turing machines

1974

Logic, Computing and Biology

2015

Logic and Computing are appropriate formal languages for Biology, and we may well be surprised by the strong analogy between software and DNA, and between hardware and the protein machinery of the cell. This chapter examines to what extent any biological entity can be described by an algorithm and, therefore, whether the Turing machine and the halting problem concepts apply. Last of all, I introduce the concepts of recursion and algorithmic complexity, both from the field of computer science, which can help us understand and conceptualise biological complexity.

Inductive inference of recursive functions: Qualitative theory

2005

This survey contains both old and very recent results in non-quantitative aspects of inductive inference of total recursive functions. The survey is not complete. The paper was written to stress some of the main results in selected directions of research performed at the University of Latvia rather than to exhaust all of the obtained results. We concentrated on the more explored areas such as the inference of indices in non-Goedel computable numberings, the inference of minimal Goedel numbers, and the specifics of inference of minimal indices in Kolmogorov numberings.

Turing's Error-revised

2016

Many important lines of argumentation have been presented during the last decades claiming that machines cannot think like people. Yet, it has been possible to construct devices and information systems, which replace people in tasks which have previously been occupied by people as the tasks require intelligence. The long and versatile discourse over, what machine intelligence is, suggests that there is something unclear in the foundations of the discourse itself. Therefore, we critically studied the foundations of used theory languages. By looking critically some of the main arguments of machine thinking, one can find unifying factors. Most of them are based on the fact that computers canno…

Moving beyond the Turing test

2012

Computers interacting with, not imitating, humans is the way forward.

Turing's error-revised

2016

Many important lines of argumentation have been presented during the last decades claiming that machines cannot think like people. Yet, it has been possible to construct devices and information systems, which replace people in tasks which have previously been occupied by people as the tasks require intelligence. The long and versatile discourse over, what machine intelligence is, suggests that there is something unclear in the foundations of the discourse itself. Therefore, we critically studied the foundations of used theory languages. By looking critically some of the main arguments of machine thinking, one can find unifying factors. Most of them are based on the fact that computers canno…