Tag: theoretical computer science

Posted on

Science/tech/university podcasts

EDX -Founded by Harvard University and MIT in 2012, edX is an online learning destination and MOOC provider, offering high-quality courses from the world’s best universities and institutions to learners everywhere.

University of Bath in the UK has this Podcasts of Public Lecture Series.

Nature

Nature has its podcast archive.

Stanford on iTunes

http://itunes.stanford.edu/ – Faculty lectures, interviews, music and sports.

University of Washington’s Cryptography Course

CSE P 590TU – Practical Aspects of Modern Cryptography – Plus related lecture slides and video archives.

Computer Science video lectures

University of Washington:
Programming Languages + Course website
Applications of Artificial Intelligence + Course website
Computer Architecture + Course website

ArsDigita University (curriculum):
Web Applications
Structure and Interpretation of Computer Programs
Object Oriented Program Design
Algorithms
Theory of Computation
Artificial Intelligence

 

 Scientific American
Scientific American (podcasts) from a popular science magazine,

“the oldest continuously published magazine in the U.S., […] bringing its readers unique insights about developments in science and technology for more than 150 years.

source: sciam
”
more University podcasts
MIT OpenCourseWare

Princeton University: WebMedia – Lectures

Tufts OpenCourseWare

Rice University: Live Webcasts & Archives

University of British Columbia Podcasts

University of Warwick podcasts

Utah State University OpenCourseWare

 

Openculture Master List of 1150 Free Courses
1150 free online courses from the world’s leading universities — Stanford, Yale, MIT, Harvard, Berkeley, Oxford and more. Over 30,000 hours of free audio and video.

http://www.openculture.com/freeonlinecourses
Findlectures: faceted index to thousands of hours of free online lectures
A curated database of free lectures, over 20,000 hours of audio, http://findlectures.com/

[Edited from Photomedia Forum post by T.Neugebauer from 2006-2016 ]

Posted on

Nondeterministic Turing Machines

In theoretical computer science, there is a theorem which states that all nondeterministic Turing machines (NTM) have an equivalent deterministic Turing machine (DTM). NTMs differ from DTMs in that the former allow for the possibility of more than one next state from a given configuration.

“
If there is more than one next move, we do not specify which next move the machine makes, only that it chooses one such move.

source: Computability and Complexity Theory, Steven Homer & Alan Selman, p.31
”

The proof for the theorem that NTMs have equivalent DTMs is through construction: the DTM builds NTM’s computation tree and then performs a breadth-first search on this tree. I was never convinced by this proof. If you take time into consideration, and the fact that NTM’s computation tree approaches infinity in size due to the size of the option set from which it ‘chooses’ at each step, you get a search that takes the DTM forever (or almost forever) to complete (which, to borrow Douglas Bridges’ expression, “does not extend to an assurance that you will find the desired term before the end of the universe”). I remain unconvinced that NTMs are equivalent to DTMs.

[Photomedia Forum post by T.Neugebauer from Jun 20, 2006]