Results 241 to 250 of about 2,596,832 (272)
Some of the next articles are maybe not open access.
Universality of Wolfram's 2, 3 Turing Machine
Complex Systems, 2020(This is known as “system 0” in the proof below.) The proof I intend to give demonstrates that this Turing machine can emulate any twocolor cyclic tag system for an infinite number of steps; in order to do this, I first show that this Turing machine can ...
Alex I. Smith
semanticscholar +1 more source
A Turing machine simulation by P systems without charges
Journal of Membrane Computing, 2019It is known that the polarizationless P systems of the kind involved in the definition of the P conjecture are able to solve problems in the complexity class P\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts ...
A. Leporati +4 more
semanticscholar +1 more source
Wave-Based Turing Machine: Time Reversal and Information Erasing.
Physical Review Letters, 2016The investigation of dynamical systems has revealed a deep-rooted difference between waves and objects regarding temporal reversibility and particlelike objects. In nondissipative chaos, the dynamic of waves always remains time reversible, unlike that of
S. Perrard, E. Fort, Y. Couder
semanticscholar +1 more source
2013 28th Annual ACM/IEEE Symposium on Logic in Computer Science, 2013
We study Turing machines over sets with atoms, also known as nominal sets. Our main result is that deterministic machines are weaker than nondeterministic ones; in particular, P6=NP in sets with atoms. Our main construction is closely related to the Cai-Furer-Immerman graphs used in descriptive complexity theory.
Mikolaj Bojanczyk +3 more
openaire +2 more sources
We study Turing machines over sets with atoms, also known as nominal sets. Our main result is that deterministic machines are weaker than nondeterministic ones; in particular, P6=NP in sets with atoms. Our main construction is closely related to the Cai-Furer-Immerman graphs used in descriptive complexity theory.
Mikolaj Bojanczyk +3 more
openaire +2 more sources
The Enduring Legacy of the Turing Machine
Computer/law journal, 2012The Church-Turing thesis has stood the test of time, capturing computation models Turing could not have conceived of, including digital computation, probabilistic, parallel and quantum computers and the Internet.
L. Fortnow
semanticscholar +1 more source
2018
Turing machines are abstract computing devices, named after Alan Mathison Turing. A Turing machine operates on a potentially infinite tape uniformly divided into squares, and is capable of entering only a finite number of distinct internal configurations. Each square may contain a symbol from a finite alphabet. The machine can scan one square at a time
openaire +2 more sources
Turing machines are abstract computing devices, named after Alan Mathison Turing. A Turing machine operates on a potentially infinite tape uniformly divided into squares, and is capable of entering only a finite number of distinct internal configurations. Each square may contain a symbol from a finite alphabet. The machine can scan one square at a time
openaire +2 more sources
2005
Turing machines exposed to a small stochastic noise are considered. An exact characterisation of their (≈Π20) computational power (as noise level tends to 0) is obtained. From a probabilistic standpoint this is a theory of large deviations for Turing machines.
Asarin, Eugene, Collins, Pieter
openaire +3 more sources
Turing machines exposed to a small stochastic noise are considered. An exact characterisation of their (≈Π20) computational power (as noise level tends to 0) is obtained. From a probabilistic standpoint this is a theory of large deviations for Turing machines.
Asarin, Eugene, Collins, Pieter
openaire +3 more sources
People cannot distinguish GPT-4 from a human in a Turing test
Conference on Fairness, Accountability and TransparencyAI systems that can fool people into thinking that they are human could have widespread social and economic consequences. In order to measure this ability, we evaluated 3 systems (ELIZA, GPT-3.5 and GPT-4) in a randomized, controlled, and preregistered ...
Cameron R. Jones +3 more
semanticscholar +1 more source
Alan Turing and the Turing Machine
1990Abstract By marking its fiftieth anniversary, this volume recognizes the long-lasting influence of the Turing machine concept. By collecting together new contributions from so many fields, it signals the exceptionally wide scope of that influence. This brief essay, intended to recall and honor the person of Alan M.
openaire +1 more source
Universality for Turing Machines, Inductive Turing Machines and Evolutionary Algorithms
Fundamenta Informaticae, 2009The aim of this paper is the development of foundations for evolutionary computations. To achieve this goal, a mathematical model of evolutionary automata is introduced and studied. The main classes of evolutionary automata considered in this paper are evolutionary Turing machines and evolutionary inductive Turing machines.
Eugene Eberbach, Mark Burgin
openaire +2 more sources