[MINI] Turing Machines
Data Skeptic27 Okt 2017

[MINI] Turing Machines

TMs are a model of computation at the heart of algorithmic analysis. A Turing Machine has two components. An infinitely long piece of tape (memory) with re-writable squares and a read/write head which is programmed to change it's state as it processes the input. This exceptionally simple mechanical computer can compute anything that is intuitively computable, thus says the Church-Turing Thesis.

Attempts to make a "better" Turing Machine by adding things like additional tapes can make the programs easier to describe, but it can't make the "better" machine more capable. It won't be able to solve any problems the basic Turing Machine can, even if it perhaps solves them faster.

An important concept we didn't get to in this episode is that of a Universal Turing Machine. Without the prefix, a TM is a particular algorithm. A Universal TM is a machine that takes, as input, a description of a TM and an input to that machine, and subsequently, simulates the inputted machine running on the given input.

Turing Machines are a central idea in computer science. They are central to algorithmic analysis and the theory of computation.

Denne episoden er hentet fra en åpen RSS-feed og er ikke publisert av Podme. Den kan derfor inneholde annonser.

Episoder(601)

Bird Distribution Modeling with Satbird

Bird Distribution Modeling with Satbird

This episode features an interview with Mélisande Teng, a PhD candidate at Université de Montréal. Her research lies in the intersection of remote sensing and computer vision for biodiversity monitori...

10 Sep 202439min

Ant Encounters

Ant Encounters

In this interview with author Deborah Gordon, Kyle asks questions about the mechanisms at work in an ant colony and what ants might teach us about how to build artificial intelligence. Ants are surpri...

26 Aug 202431min

Computing Toolbox

Computing Toolbox

This season it's become clear that computing skills are vital for working in the natural sciences. In this episode, we were fortunate to speak with Madlen Wilmes, co-author of the book "Computing Skil...

19 Aug 202438min

Biodiversity Monitoring

Biodiversity Monitoring

In this episode, we talked shop with Hager Radi about her biodiversity monitoring work. While biodiversity modeling may sound simple, count organisms and mark their location, there is a lot more to it...

14 Aug 202432min

Hacking the Colony

Hacking the Colony

Today, Ashay Aswale and Tony Lopez shared their work on swarm robotics and what they have learned from ants. Robotic swarms must solve the same problems that eusocial insects do. What if your pheromon...

8 Aug 202441min

Primate Poses

Primate Poses

During this season we have talked with researchers working to utilize machine learning for behavioral observations. In previous episodes, you have heard about the software people like Richard use, but...

31 Jul 202432min

Generating 3D Animals with YouDream

Generating 3D Animals with YouDream

Generative AI can struggle to create realistic animals and 2D representations often have mistakes like extra limbs and tails. If 2D wasn't hard enough, there are researchers working on generative 3D m...

23 Jul 20241h

Weird Communication

Weird Communication

Today, we sat down with Dr. Ignacio Escalante Meza to learn about opiliones and treehoppers. Opiliones, known as "daddy long legs" in the US, are understudied arachnids known for their tenacious locom...

15 Jul 202438min

Populært innen Vitenskap

fastlegen
tingenes-tilstand
jss
forskningno
rekommandert
rss-zahid-ali-hjelper-deg
rss-paradigmepodden
sinnsyn
vett-og-vitenskap-med-gaute-einevoll
rss-overskuddsliv
nordnorsk-historie
kvinnehelsepodden
tidlose-historier
villmarksliv
liberal-halvtime
rss-inn-til-kjernen-med-sunniva-rose
fjellsportpodden
grunnstoffene
nevropodden
rss-rekommandert