Difference between revisions of "2556: Turing Complete"

Explain xkcd: It's 'cause you're dumb.
Jump to: navigation, search
(Explanation: I'm sure this is what it means.)
(Explanation)
Line 10: Line 10:
 
{{incomplete|Created by a VIDEO GAME-PLAYING DISHWASHER- Please change this comment when editing this page. Do NOT delete this tag too soon.}}
 
{{incomplete|Created by a VIDEO GAME-PLAYING DISHWASHER- Please change this comment when editing this page. Do NOT delete this tag too soon.}}
  
A Turing Machine is a theoretical form of computer (as an idealised thought exercise) that has an infinite tape of symbols and can act upon and change these values aa it moves up and down this tape according to specific deterministic rules.
+
A Turing Machine is a theoretical form of computer (as an idealised thought exercise) that has an infinite tape of symbols and can act upon and change these values as it moves up and down this tape according to specific deterministic rules.
  
 
This very simple machine can be shown to do every computational task that what we think of as a "computer" can do, given the right setup and enough time. Something that is Turing Complete is able to act as a Turing Machine, though generally with the limitation of having a finite tape, and this means it is also able to do basically every computational task.
 
This very simple machine can be shown to do every computational task that what we think of as a "computer" can do, given the right setup and enough time. Something that is Turing Complete is able to act as a Turing Machine, though generally with the limitation of having a finite tape, and this means it is also able to do basically every computational task.

Revision as of 23:49, 17 December 2021

Turing Complete
Thanks to the ForcedEntry exploit, your company's entire tech stack can now be hosted out of a PDF you texted to someone.
Title text: Thanks to the ForcedEntry exploit, your company's entire tech stack can now be hosted out of a PDF you texted to someone.

Explanation

Ambox notice.png This explanation may be incomplete or incorrect: Created by a VIDEO GAME-PLAYING DISHWASHER- Please change this comment when editing this page. Do NOT delete this tag too soon.
If you can address this issue, please edit the page! Thanks.

A Turing Machine is a theoretical form of computer (as an idealised thought exercise) that has an infinite tape of symbols and can act upon and change these values as it moves up and down this tape according to specific deterministic rules.

This very simple machine can be shown to do every computational task that what we think of as a "computer" can do, given the right setup and enough time. Something that is Turing Complete is able to act as a Turing Machine, though generally with the limitation of having a finite tape, and this means it is also able to do basically every computational task.

While many pieces of hardware and software are supposed to be Turing Complete (even Excel, as previously pointed out in 2453: Excel Lambda), this comic implies that this was not what it was designed for. Whatever Ponytail has been referring to is not shown, but it seems to be an anecdote about how something seemingly too simple and/or specialised to exhibit such a computational equivalence has been discovered to actually be that capable.

With complex processors now installed in many household items, including kitchen whitegoods like dishwashers, the possibility is raised that someone has 'hacked' such a device to do the same computational work as an actual games console. Or, referring to Alan Turing's secret (but now famous) work in helping to decode enemy signals in World War Two it could actually mean that there is yet again a belligerent country whose military communications are most urgently needed to be read.

The ForcedEntry exploit is a way that was discovered to allow PDF files to force malware onto various devices. In the title-text it is suggested that this mechanism can be used for what might be more legal and practical purposes, although this might be up to some interpretation depending upon who has the right (and permission) to do what.

A Tech Stack is one shorthand way of describing the way an integrated grouping of communicating software packages provides everything from the deepest data handling (even as low-level as an Operating System itself) to the user interface. All of these will normally be on a computer (or possibly many of them, whether locally or distributed worldwide) and if a sufficiently functional surrogate system is capable of emulating this (computing what the original computer(s) would do) then it can be considered to effectively be the same stack of technology and duplicate or replace the originals.

Transcript

Ambox notice.png This transcript is incomplete. Please help editing it! Thanks.

[Ponytail and Cueball are standing next to each other] ...Now, it turns out this is actually Turing-Complete... [caption below the panel:] This phrase either means someone spent six months getting their dishwasher to play Mario or you are under attack by a nation-state.

comment.png add a comment! ⋅ comment.png add a topic (use sparingly)! ⋅ Icons-mini-action refresh blue.gif refresh comments!

Discussion

This is a reference to the new FORCEDENTRY exploit analysis by Google's project zero: https://googleprojectzero.blogspot.com/2021/12/a-deep-dive-into-nso-zero-click.html The exploit runs a full (turing-complete) VM within a PDF decompression algorithm. 172.70.86.68 22:37, 17 December 2021 (UTC)

I don't think "attack by a nation-state" is referring to Turing's WWII work. I think it means a modern nation-state is using FORCEDENTRY to attack you via some unexpected device. Barmar (talk) 23:56, 17 December 2021 (UTC)

I think it actually is a reference to national security agencies being able to get into your phone and get all your private data and so on 108.162.237.5 01:00, 18 December 2021 (UTC)Bumpf

The explanation should probably also mention that https://googleprojectzero.blogspot.com/2021/12/a-deep-dive-into-nso-zero-click.html was published just two days before this comic. Frank 162.158.94.165 11:09, 18 December 2021 (UTC)

I added in a much needed A Bunch of Rocks reference. I mean, it's a possibly broken Turing Machine (because the operator is 'only human' and occasionally makes mistakes in his process. But, by definition, anything capable of simulating (many!) things that are themselves considered Turing Complete is thus by itself Turing Complete as it carries out (or could carry out) all the tasks that are successfully (or potentially) carried out by them 'on their own'. It's a metaphysical (metaphilosophical? metasomethingorother...) issue, of course. ;) 172.70.91.84 00:29, 19 December 2021 (UTC)

(Actually, that was before I then went back and fully read ABOR, to fulfill my nostalgia. I forgot that it actually says it is TC in an in-frame footnote. That might be what prompted me to think of it, so forget about me being too clever, it's just true. Voice Of God, etc.) 172.70.91.84 00:34, 19 December 2021 (UTC)
It is also one of my favorite and I remember the footnote without reading it again now ;-) Wow a dust mote just disappeared in front of me... :-D (updated your post with a link to the comic!) --Kynde (talk) 08:03, 20 December 2021 (UTC)

Do things feel more and more like Stross's Accelerando to you as well? 172.68.246.129 09:09, 22 December 2021 (UTC)

Honestly surprised Randall didn't reference Doom in this comic. It's the one game that's synonymous with running on unusual hardware. 172.70.85.79 23:41, 23 December 2021 (UTC)

Weird Machines and Turing Completeness

This comic is closely related to the language security work on weird machines, yes? Could someone more knowledgeable comment?--Philip Romolo Neri (talk) 09:25, 10 January 2022 (UTC)

A Turing tape is unbounded, not infinite. At any given time, only a finite number of symbols have been read or written, but that number can grow without limit over time. In principle, a real-world machine that was able to request more memory whenever it ran out of what it had could be considered equally unbounded - at least if the universe is infinite. Brangdon (talk) 13:14, 23 April 2022 (UTC)