Computing and Information Technology Interactive Digital Educational Library

 

CITIDEL >
Planet Math Computer Science  >
Planet Math Computer Science Collection >

Please use this identifier to cite or link to this item: http://hdl.handle.net/10117/1245

Title: random Turing machine
Issue Date: 2-May-2005
Publisher: PlanetMath
Citation: http://planetmath.org/encyclopedia/RandomTuringMachine.html
Abstract: A random Turing machine is defined the same way as a non-deterministic Turing machine, but with different rules governing when it accepts or rejects. Whenever there are multiple legal moves, instead of always guessing right, a random machine selects one of the possible moves at random. As with non-deterministic machines, this can also be viewed as a deterministic machine with an extra input, which corresponds to the random selections. There are several different ways of defining what it means for a random Turing machine to accept or reject an input. Let ... be the probability that
URI: http://www.citidel.org/handle/10117/1245
Appears in Collections:Planet Math Computer Science Collection

Files in This Item:

File SizeFormat
RandomTuringMachine.html25KbHTMLView/Open

All items in DSpace are protected by copyright, with all rights reserved.

 

Valid XHTML 1.0! DSpace Software Copyright © 2002-2006 MIT and Hewlett-Packard - Feedback