Cavagnaro, Haight - Dictionary of Classical and Theoretical Mathematics (523108), страница 9
Текст из файла (страница 9)
The notion of Turing machine wasformalized by Alan Turing in his 1936 Proceedings of the London Mathematical Society paper.A Turing machine consists of a bi-infinitetape, which is divided into cells, a reading headwhich can scan one cell of the tape at a time, a© 2001 by CRC Press LLCfinite tape alphabet S = {s0 , s1 , . .
. , sn } of symbols which can be written on the tape, and a finiteset Q = {q0 , q1 , . . . , qm } of possible states. Thesets S and Q have the properties that S ∩Q = ∅,{1, B} ⊆ S (where B stands for “blank”), andq0 ∈ Q is the designated initial state. A Turingmachine which is in state qj reading symbol sion its tape may perform one of three possibleactions: it may write over the symbol it is scanning, move the read head right (R), and go intoanother (possibly the same) state; it may writeover the symbol it is scanning, move the readhead left (L), and go into another (possibly thesame) state; or it may halt.The action of the Turing machine is governedby a Turing program, given by a transition function δ, whose domain is some subset of Q×S andwhose range is a subset of the set Q×S×{R, L}.If δ(q, a) = (q̂, â, m), then the action of the machine is as follows. If the machine is in state q,reading symbol a on the tape, then it replaces aby â on the tape, moves the read head one cellto the right if m = R, moves the read head onecell to the left if m = L, and goes into state q̂.The Turing program halts if the machine is in astate q, reading a symbol a, and the transitionfunction is undefined on (q, a).A Turing machine computes a partial function as follows: given input x1 , .
. . , xn , the tapeis initially set to. . . B1x1 +1 B1x2 +1 B . . . B1xn +1 B . . . ,where 1k indicates a string of k 1s, one symbol1 per cell, . . . B1x1 +1 indicates that all cells tothe left of the initial 1 on the tape are blank, and1xn +1 B . . . indicates that all cells to the rightof the last 1 on the tape are blank. The reading head is positioned on the leftmost 1 on thetape, and the machine is set to the initial state q0 .The output of the function (if any) is the numberof 1s on the tape when the machine halts, afterexecuting the program, if it ever halts.The following is a Turing machine programwhich computes the function f (x1 , x2 ) = x1 +x2 , thus showing that f is Turing computable.The idea is that, given input.
. . B1x1 +1 B1x2 +1 B . . . ,the machine replaces the middle blank B by a1 (instructions 1 – 2), moves to the leftmost 1concentric(instructions 3 – 4), and then erases three 1s(instructions 5 – 7).• δ(q0 , 1) = (q0 , 1, R)• δ(q0 , B) = (q1 , 1, L)• δ(q1 , 1) = (q1 , 1, L)• δ(q1 , B) = (q2 , B, R)• δ(q2 , 1) = (q3 , B, R)• δ(q3 , 1) = (q4 , B, R)• δ(q4 , 1) = (q5 , B, R)Other formalizations of the Turing machineexist which are slight variations of those givenhere and which produce the same class of Turing–computable functions.concentric A common geometric term, meaning “with the same center”.
See concentric circles, concentric cylinders.concentric circles Circles that lie in the sameplane and have the same center.unit vector in that direction. For example, letI k (I = [−1, 1]) be a k-dimensional convexcell which is a cone of the boundary of I k fromits center 0. Each point x of I k can be writtenuniquely as x = t · u for 0 < t ≤ 1 where u belongs to the boundary of I k .
A cone extensionresults when a piecewise linear embedding Ffrom the boundary of I m to the boundary of I n isextended to a piecewise linear embedding F between the two convex cells by setting F (0) = 0and F (t · u) = t · f (u) for t · u ∈ I m − {0}.conformal arc elementLet S n be a conformal space of dimension n (an n-dimensionalsphere represented as the quadric hypersurfaceS n : x12 +x22 +...+xn2 −2x0 x∞ = 0 in an (n+1)dimensional real projective space P n+1 , wherethe (xi ) are homogeneous coordinates in P n+1 ).The conformal arc element of a curve is givenby the Frenet-Serret formula for the curve.
Forexample, let S be a surface in a 3-dimensionalprojective space and let A be a point of S associated with all the frames [A, A1 , A2 , A3 ] whereA1 , A2 , A3 are points of the tangent plane to Sat A. The Frenet-Serret formula for S 3 is givenby the following matrix:concentric cylindersCircular cylinderswhose circular cross-sections are concentric circles.concentric spherescenter.Spheres with the sameconeA solid in R3 , bounded by a region ina plane (the base) and the surface formed bystraight lines (the generators) which join pointsof the boundary of the base to a fixed point (thevertex) not in the plane of the base.
The conical surface described by a moving straight linepassing through the vertex and tracing any fixedcurve, such as a circle, ellipse, etc., at anotherpoint is sometimes also called a cone. A conemay be viewed as a quadratic surface, whoseequation is Ax 2 + By 2 + Cz2 = 0 (A, B, C =0). When A = B, it is a right circular cone(also called a cone of revolution); if A =B, it isan oblique circular cone.cone extension A deformation of a cone.
Fora given direction at a point, it represents the increase of length per unit length of arc, i.e., the© 2001 by CRC Press LLCωαβ=0κdα−dα00dα000κdα000−τ dα−dα00τ dα000dα000where dα is the conformal arc element, κ is theconformal curvature, and τ is the conformal torβsion. ωα is the Pfaffian form that depends onthe principal parameters determining the originA and the secondary parameters determining theframe.conformal correspondenceA diffeomorphism between two surfaces, whose derivativeis a linear map.
Angles, but not necessarilylengths, are preserved under conformal correspondence. Also called conformal mapping.conformal curvature Let I be an open interval of R. Let α : I → R3 be a curve parameterized by arc length s (s ∈ I ) and α (s) = 0. Foreach value of s, let t, n, and b be vector fieldscongruence on a categoryalong α defined byt (s) = α (s), n(s) =α (s)α (s)andb (s) = t (s) × n (s) .The derivative t (s) = κ (s) n (s) yields thefunction κ : I → R, the geometric entity whichis the curvature of α in a neighborhood of S.Physically, curvature measures how much thecurve differs (bends) from a straight line.
Thisdefinition is generalizable to n-dimensional conformal space, where the conformal curvature ofa curve can be derived from the Frenet-Serretapparatus. The concept of curvature associatedwith a moving frame along a curve was introduced by F. Frenet in 1847 and independentlyby J.A. Serret in 1851.conformal differential geometry The studyof geometric quantities that are invariant under conformal transformations, using methodsof mathematical analysis such as differential calculus.conformal equivalenceLet w = f (z) be afunction that conformally maps a domain D onthe complex z-sphere homeomorphically onto adomain on the complex w-sphere.
Then isconformally equivalent to D.conformal geometryThe study of properties of figures that are invariant under conformaltransformations. Let S n be an n-dimensionalsphere, P n+1 be an (n + 1)-dimensional projective space, and let M(n) be the group of allprojective transformations of P n+1 which leaveS n invariant.
Then (S n , M(n)) is a conformalgeometry or a Möbius geometry.conformal invariantA geometric quantitypreserved by conformal mappings.conformal mappingA conformal mappingor correspondence between two surfaces S andS ∗ is a diffeomorphism of S onto S ∗ such thatthe angle between any two curves at an arbitrarypoint x on S is equal to the angle between the corresponding curves on S ∗ . Conformal mappingsare more general than isomorphisms which pre-© 2001 by CRC Press LLCserve both angles and distances. In R3 , conformal mappings are those obtained by translations, reflections in planes, and inversions inspheres. A one-to-one conformal mapping is aconformal transformation.
In R3 the conformaltransformations form the 10-parameter conformal group. In 1779, Lagrange had obtained allthe conformal transformations of a portion ofthe earth’s surface onto a plane area that transformed latitude and longitude circles into circular arcs.conformal torsion Let I be an open intervalof R. Let α : I → R3 be a curve parameterizedby arc length S (S ∈ I ) and αsf (s) = 0.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
