Who Can Name the Bigger Number? Scott Aaronson∗ 1999 In an old joke, two noblemen vie to name the bigger number. The first, after ruminating for hours, triumphantly announces ”Eighty-three!” The second,

First Page		Document Content
Date: 2016-01-08 10:48:49 Theory of computation Computability theory Busy beaver Computable function Computability Turing machine Halting problem Hypercomputation Computable number Algorithm Alan Turing Ackermann function		Who Can Name the Bigger Number? Scott Aaronson∗ 1999 In an old joke, two noblemen vie to name the bigger number. The first, after ruminating for hours, triumphantly announces ”Eighty-three!” The second, Add to Reading List Source URL: homepages.math.uic.edu Download Document from Source Website File Size: 132,03 KB Share Document on Facebook

	The Power of One-State Turing Machines Marzio De Biasi Jan 15, 2018 Abstract At first glance, one–state Turing machines are very weak: the Halting problem for them is decidable, and, without memory, they cannot even ac DocID: 1ucEA - View Document
	TURING MACHINES TO WORD PROBLEMS CHARLES F. MILLER III Abstract. We trace the emergence of unsolvable problems in algebra and topology from the unsolvable halting problem for Turing machines. DocID: 1tbMl - View Document
	Issues in Multimedia Authoring Lecture 10: Limitations of Computers Keith Douglas Summary DocID: 1qeXR - View Document
	MCS 441 – Theory of Computation I Syllabus Lev Reyzin SpringTime and Location: M-W-F, 12:00-12:50pm, Lincoln Hall (TH) 205 DocID: 1q9nq - View Document
	Computability 1 Tao Jiang DocID: 1pnSU - View Document