Turing machine - Revision history

Jnc: typos

2026-09-29T00:05:46Z

typos

← Older revision		Revision as of 00:05, 29 September 2026
Line 6:		Line 6:

	<blockquote>		<blockquote>
	A Turing machine is a finite-state machine associated with an external storage or memory medium. This medium has the form of a sequence of ''squares'', marked of on a linear ''tape''. The machine is ~~couple~~ to the tape through a ''head'', which is situated, at each moment, on some square of the tape (see ~~fig~~). The head has three functions, all of which are exercised in each operation cycle of the finite-state machine. The functions are: ''reading'' the square of the tape being ''scanned'', ''writing'' on the scanned square, and ''moving'' the machine to an adjacent square (which becomes the scanned square in the next operation cycle).		A Turing machine is a finite-state machine associated with an external storage or memory medium. This medium has the form of a sequence of ''squares'', marked off on a linear ''tape''. The machine is coupled to the tape through a ''head'', which is situated, at each moment, on some square of the tape (see figure). The head has three functions, all of which are exercised in each operation cycle of the finite-state machine. The functions are: ''reading'' the square of the tape being "scanned", ''writing'' on the scanned square, and ''moving'' the machine to an adjacent square (which becomes the scanned square in the next operation cycle).
	</blockquote>		</blockquote>

Jnc: Move book cite to bottom

2026-09-18T20:59:16Z

Move book cite to bottom

← Older revision		Revision as of 20:59, 18 September 2026
Line 1:		Line 1:
	[[File:Minksy-computation-fig-6.0.1.png\|right\|thumb\|250px\|A blank Turing machine from Minsky's ''Computation: Finite and Infinite Machines'']]		[[File:Minksy-computation-fig-6.0.1.png\|right\|thumb\|250px\|A blank Turing machine from Minsky's ''Computation: Finite and Infinite Machines'']]

	A '''Turing machine''' is an abstract [[computer]] (ironically, created before the first real computer), devised by mathematician [[Alan Turing]] in 1936, to develop theories of ''computability'' -- that which can, and which cannot, be computed.		A '''Turing machine''' is an abstract [[computer]] (ironically, created before the first real computer), devised by mathematician [[Alan Turing]] in 1936, to develop theories of ''computability'' - that which can, and which cannot, be computed.

	The classic introduction to this kind of machine is ~~MIT professor~~ [[Marvin Minksy]]~~'s ''Computation: Finite and Infinite Machines'' (Prentice-Hall 1967)~~:		The classic introduction to this kind of machine is from [[Marvin Minksy]]:

	<blockquote>		<blockquote>
	A Turing machine is a finite-state machine associated with an external		A Turing machine is a finite-state machine associated with an external storage or memory medium. This medium has the form of a sequence of ''squares'', marked of on a linear ''tape''. The machine is couple to the tape through a ''head'', which is situated, at each moment, on some square of the tape (see fig). The head has three functions, all of which are exercised in each operation cycle of the finite-state machine. The functions are: ''reading'' the square of the tape being ''scanned'', ''writing'' on the scanned square, and ''moving'' the machine to an adjacent square (which becomes the scanned square in the next operation cycle).
	storage or memory medium. This medium has the form of a sequence of
	''squares'', marked of on a linear ''tape''. The machine is couple to the tape
	through a ''head'', which is situated, at each moment, on some square of the
	tape (see fig). The head has three functions, all of which are exercised
	in each operation cycle of the finite-state machine. The functions are:
	''reading'' the square of the tape being ''scanned'', ''writing'' on the scanned
	square, and ''moving'' the machine to an adjacent square (which becomes the
	scanned square in the next operation cycle).
	</blockquote>		</blockquote>

Line 31:		Line 23:

	* [[Analytical Engine]]		* [[Analytical Engine]]

			==Further reading==

			* Marvin Minksy, ''Computation: Finite and Infinite Machines'', Prentice-Hall, Englewood Cliffs, 1967

	==External links==		==External links==

Jnc: Bold 'Turing complete' (for use as a target)

2024-04-10T04:21:03Z

Bold 'Turing complete' (for use as a target)

← Older revision		Revision as of 04:21, 10 April 2024
Line 17:		Line 17:
	</blockquote>		</blockquote>

	The basic operation is that each square can have a single symbol from a finite		The basic operation is that each square can have a single symbol from a finite set of symbols; each step possibly changes the symbol and moves the tape to the left or the right.
	set of symbols; each step possibly changes the symbol and moves the tape to the
	left or the right.

	They are comprehensively covered in computing literature, with endless variations, including a large number of physical implementations.		They are comprehensively covered in computing literature, with endless variations, including a large number of physical implementations.
Line 25:		Line 23:
	A number of very important theoretical results came from study of these machines:		A number of very important theoretical results came from study of these machines:

	* A Turing machine is adequate to simulate any other kind of automata, ignoring specified size and speed constraints.		* A Turing machine is adequate to simulate any other kind of [[automata]], ignoring specified size and speed constraints.
	* A machine which can simulate a Turing machine can therefore simulate ''any'' machine and is said to be ''Turing complete''.		* A machine which can simulate a Turing machine can therefore simulate ''any'' machine and is said to be '''Turing complete'''.

	{{semi-stub}}		{{semi-stub}}

Jnc: Add category, some external links to toy physical ones, etc

2024-04-08T18:13:41Z

Add category, some external links to toy physical ones, etc

← Older revision		Revision as of 18:13, 8 April 2024
Line 1:		Line 1:
	[[File:Minksy-computation-fig-6.0.1.png\|right\|thumb\|A blank Turing machine from Minsky's ''Computation: Finite and Infinite Machines'']]		[[File:Minksy-computation-fig-6.0.1.png\|right\|thumb\|250px\|A blank Turing machine from Minsky's ''Computation: Finite and Infinite Machines'']]

	A '''Turing ~~Machine~~''' is ~~a kind of~~ abstract computer, devised by mathematician [[Alan Turing]] in 1936, to develop theories of ''computability'' -- that which can, and which cannot, be computed.		A '''Turing machine''' is an abstract [[computer]] (ironically, created before the first real computer), devised by mathematician [[Alan Turing]] in 1936, to develop theories of ''computability'' -- that which can, and which cannot, be computed.

	The classic introduction to this kind of machine is MIT professor Marvin Minksy's ''Computation: Finite and Infinite Machines'' (Prentice-Hall 1967):		The classic introduction to this kind of machine is MIT professor [[Marvin Minksy]]'s ''Computation: Finite and Infinite Machines'' (Prentice-Hall 1967):

	<blockquote>		<blockquote>
Line 12:		Line 12:
	tape (see fig). The head has three functions, all of which are exercised		tape (see fig). The head has three functions, all of which are exercised
	in each operation cycle of the finite-state machine. The functions are:		in each operation cycle of the finite-state machine. The functions are:
	''reading'' the square of the tape ~~beeing "~~scanned," ''writing'' on the scanned		''reading'' the square of the tape being ''scanned'', ''writing'' on the scanned
	square, and ''moving'' the machine to an adjacent square (which becomes the		square, and ''moving'' the machine to an adjacent square (which becomes the
	scanned square in the next operation cycle).		scanned square in the next operation cycle).
Line 27:		Line 27:
	* A Turing machine is adequate to simulate any other kind of automata, ignoring specified size and speed constraints.		* A Turing machine is adequate to simulate any other kind of automata, ignoring specified size and speed constraints.
	* A machine which can simulate a Turing machine can therefore simulate ''any'' machine and is said to be ''Turing complete''.		* A machine which can simulate a Turing machine can therefore simulate ''any'' machine and is said to be ''Turing complete''.

			{{semi-stub}}

			==See also==

			* [[Analytical Engine]]

			==External links==

			* [https://web.stanford.edu/class/cs208e/lectures/09-Turing-Machines/d.pdf Turing Machines] - good lecture notes on the topic, and the environment in which it was create
			* [https://aturingmachine.com/index.php A Turing Machine] - wonderful site about an actual Turing machine, with a lot of detail
			** [https://aturingmachine.com/hardware.php Hardware Information]
			* [https://legoofdoom.blogspot.com/2008/12/noter-omkring-konstruktionen-af.html Lego of Doom] - a Turing machine built out of Lego
			** [https://legoofdoom.blogspot.com/2008/12/noter-omkring-konstruktionen-af.html Constructing the Turing Machine]
			** [https://legoofdoom.blogspot.com/2009/01/conclusion.html Conclusion]

			[[Category: Theory]]

Jonathanjo: From wanted pages

2024-04-07T12:45:27Z

From wanted pages

New page

[[File:Minksy-computation-fig-6.0.1.png|right|thumb|A blank Turing machine from Minsky's ''Computation: Finite and Infinite Machines'']]

A '''Turing Machine''' is a kind of abstract computer, devised by mathematician [[Alan Turing]] in 1936, to develop theories of ''computability'' -- that which can, and which cannot, be computed.

The classic introduction to this kind of machine is MIT professor Marvin Minksy's ''Computation: Finite and Infinite Machines'' (Prentice-Hall 1967):

<blockquote>
A Turing machine is a finite-state machine associated with an external
storage or memory medium. This medium has the form of a sequence of
''squares'', marked of on a linear ''tape''. The machine is couple to the tape
through a ''head'', which is situated, at each moment, on some square of the
tape (see fig). The head has three functions, all of which are exercised
in each operation cycle of the finite-state machine. The functions are:
''reading'' the square of the tape beeing "scanned," ''writing'' on the scanned
square, and ''moving'' the machine to an adjacent square (which becomes the
scanned square in the next operation cycle).
</blockquote>

The basic operation is that each square can have a single symbol from a finite
set of symbols; each step possibly changes the symbol and moves the tape to the
left or the right.

They are comprehensively covered in computing literature, with endless variations, including a large number of physical implementations.

A number of very important theoretical results came from study of these machines:

* A Turing machine is adequate to simulate any other kind of automata, ignoring specified size and speed constraints.
* A machine which can simulate a Turing machine can therefore simulate ''any'' machine and is said to be ''Turing complete''.