Çfarë është një makinë Turing?
Një makinë Turing është një makinë abstrakte e krijuar nga Alan Turing në vitin 1936. Është një pajisje llogaritëse teorike që përbëhet nga një shirit i pafund, një kokë që lexon dhe lëviz nëpër këtë shirit, dhe një grup udhëzimesh për shkrimin, fshirjen dhe lëvizjen e përmbajtjes së shiritit. Është një model llogaritjeje që mund të përdoret për të zgjidhur një sërë problemesh, nga llogaritja e rrënjës katrore të një numri deri te përcaktimi nëse një varg i caktuar është një palindrom.