COMS W1004 Lecture Notes - Lecture 23: I Try, Infinite Loop

• School: Columbia University
• Department: Computer Science
• Course: COMS W1004
• Professor: Adam Cannon

Document Summary

Chapter 9 problems in big java textbook listed as recommended problem in problem set 6 is highly. Instruction model the algorithm: 5-tuple (current state, current(read) symbol, next(write) symbol, next state, direction) Example: given a binary string as input, write tm that copies the string (string, b, copy of string) b. So in this case, 2 paths since just 0"s and 1"s: tm stops when there are no more instructions, church-turing thesis. If there exists an algorithm for solving a symbolic manipulation problem, then there exists a. Turing machine for solving that problem: write program that can determine when any given program with some input will have an infinite loop or not, t(i) = {halts on i, or goes on forever} b. This is not a contradiction: s(s*) = q(t*, t*) = {s does not halt on s* when s halts on s*, or 0 when s does not halts on s*}