Automata Theory

3 Key excerpts on "Automata Theory"

• 

  eBook - ePub

  Encyclopedia of Computer Science and Technology

  Volume 2 - AN/FSQ-7 Computer to Bivalent Programming by Implicit Enumeration

  • Jack Belzer(Author)
  • 2020(Publication Date)
  • CRC Press

    (Publisher)

  Automata Theory

  Much of mathematics studies functions, rules ƒ : X→ Y for assigning to each element x of the set X an element f(x) of the set Y. In computer science, we seek to realize functions by computations, which are sequences of data manipulations under the control of a program. Programs are run by machines. In specifying a machine we have to specify the syntax, or legitimate forms, for the data structures that may occur as input to the machine, as descriptions of the internal state of the machine, and as output from the machine. A program must be so presented as input structure that it will be incorporated into the internal state structure in a fashion that will cause the machine to process data in such a way as to realize some given function. The semantics of the machine direct how it will change state, read input and provide output at each stage, and thus determines how the program will be interpreted.

  Automata Theory is the mathematical study of questions of realization, decomposition, simulation, complexity, and computation abstracted from the above considerations. In this article we shall sample some portions of this theory, starting with the notion of a Turing machine [1 , 2 ], a formalization of the digital computer which preceded the computer itself by almost a decade : The machine consists of a control box in which may be placed a finite program; an indefinitely extendable tape, divided lengthwise into squares (i.e., depending on our choice of mathematical fiction, we may consider the tape as comprising an infinite string of squares of which all but finitely many are blank; or as a finite tape, to the ends of which arbitrarily many new squares may be added as required); and a device for scanning, or printing on, one square of the tape at a time, and for moving the tape, all under the command of the control box. We start the machine with a finite string (i.e., sequence) of symbols from some alphabet X (we denote by X* the set of all such strings) on the tape, and with a program in the control box. The symbol scanned, and the instruction now being executed, determine what new symbol shall be printed on the square, how the tape shall be moved, and what instruction is to be executed next. If and when the machine stops, the result of our computation, a new string from X*

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  From Writing To Computers

  • Julian Warner(Author)
  • 2002(Publication Date)
  • Routledge

    (Publisher)

  A comparative, although not exhaustive, reading would also suggest that Automata Theory has been a partly separate activity from formal logic and mathematics, although there would seem to have been less public recognition of this contrast. The contrast also assumes a different form. In this case, there is not an easily recognizable distinction between the mathematical constructions embodied in abstract automata and the construction of a material object. Rather there is a more subtle and elusive contrast between two different modes of representation favoured by intersecting, although not unified, thought communities. Diagrammatic forms tend to be preferred for automata and notational forms for formal logic. A unified account of Automata Theory and formal logic, although equally desirable, remains elusive.

  Three broadly distinguishable, and particularly significant, strands associated with the study of the computational process can, then, be detected: Automata Theory, formal and mathematical logic, and working computers. They do not seem to have been fully integrated with one another. Even texts which treat computers, Automata Theory and formal logic (Wang 1974 ; Herken 1988 ; Penrose 1989 ), or Automata Theory and formal logic (Davis 1958 ; Boolos and Jeffrey 1974 ), do not provide an integrated account.

  The intention here is to give an exposition of Automata Theory and formal logic,1 although the possibility of developing an integrated account of Automata Theory, formal logic and working computers will also be indicated. Although the focus will be upon Automata Theory, beginning with its historical development and then giving examples of significant categories of the computational process, the discussion will also explore resemblances between Automata Theory and formal logic, and give the model which correlates Automata Theory to working computers. Finally, the value of the models developed in automata studies in avoiding problems over the definition of a program, of data and of a computer will be considered.

  A discussion of Automata Theory raises acute problems of cognitive authority and of purpose and level of exposition. Cognitive authority with regard to automata studies has tended to be implicitly claimed by discursive communities associated with mathematical logic and computer science. The question here is not with their competence within that domain but with any implied claim to exclusive proprietorship over that domain and with the extension of mathematical procedures and expectations to nonmathematical discourse. For instance, examples of computational processes tend to reflect mathematical interests while the current range of computer applications has grown beyond mathematical boundaries.

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Impossible Minds

  My Neurons, My ConsciousnessRevised Edition

  • Igor Aleksander(Author)
  • 2014(Publication Date)
  • ICP

    (Publisher)

  As seen in the previous chapter, it is suggested that something called a state machine may be an appropriate (or perhaps just interesting for the severely skeptical) metaphor for the brain (just as the pump is a metaphor for the heart). State machines are best described by a language called Automata Theory and the object of this chapter is to introduce this language, explain it from scratch and then try to take the big leap into suggesting that the elements of consciousness find expression within the language.

  Automata Theory is used by engineers who design information processing machines. This seems appropriate as the information processing functions of the brain must be somehow involved in our hunt for consciousness. With hearts, the language of the dynamics of liquids is appropriate in discussions about the blood flow functions of the heart. Automata Theory is there to express the rules which apply to the neural state machines introduced in the Basic Guess. I shall argue that consciousness, under some conditions, emerges from the natural laws which govern what can and cannot happen in a neural state machine. As I know that Automata Theory easily describes these natural laws, I suggest that it follows that it is the appropriate language for the modelling of conscious entities.

  The Wheel Machine

  To ease into the idea of a state machine as a metaphor for a physical object, it may be helpful to think about the gadget in Fig. 3.1 . Pebbles come down the chute and, by falling into a paddle blade, cause the wheel to rotate counter-clockwise by one position, at which point the pebble falls out of the paddle blade. There is a striker attached to blade a which rings a bell as this blade comes into the pebble-receiving position. If it is assumed that the pebbles don’t arrive at too great a rate, the entire machine can be seen to be a pebble counter which rings the bell every time eight pebbles have come down the chute. Let a = 0, b = 1, c = 2 and so on. Then, starting with a in the receiving position, the number of the blade in the receiving position is an indication of precisely how many pebbles in a group of eight have been counted. Indeed, the eight positions a to h

  Sign up to read

  Learn more about book