Shpjegoni konceptin e një makine Turing.
Makina Turing është një makinë kompjuterike teorike që mund të përdoret për të zgjidhur çdo problem vendimi. Ajo përbëhet nga një kasete pafundësisht e gjatë e cila përdoret për të ruajtur të dhënat e hyrjes dhe dalja mund të lexohet nga kaseta. Është një makinë e programueshme që është në gjendje të lexojë komanda në formën e simboleve dhe të ndjekë një grup udhëzimeve për të manipuluar të dhënat. Ajo u projektua nga Alan Turing dhe u përdor si një model abstrakt për të kuptuar se si funksionojnë kompjuterët. Karakteristika më e rëndësishme e një makine Turing është se ajo është Turing-e plotë, që do të thotë se ajo mund të simulojë çdo makinë tjetër kompjuterike.