COMS W1004 Chapter Notes - Chapter 12: Well-Order, Halting Problem, Asteroid Family
4 May 2016
School
Department
Course
Professor
Document Summary
Lacks full functionality of the real thing: can be used to predict the behavior of an existing system for testing, a model of a computing agent, properties of a computing agent, accept input. Store info in memory and retrieve it from memory. Take actions according to algorithm instructions depending on present state of the computing agent, as well as the input item being processed: produce output, the turing machine, actions. Turing machine is a theoretical model of computation that includes a conceptual tape extending infinitely in both directions. Symbols come form a finite set of symbols called tape alphabet. Finite number k of states of the machine, labeled 1,2, ,k. Turing machine instructions (current state, current symbol, next symbol, next state, direction of move: required features: Can take actions based on current state and symbol read by instructions given. Assume p is a turing machine that solves the halting problem.
