Jump to content

File:Recursive enumeration of all halting Turing machines.gif

Page contents not supported in other languages.
This is a file from the Wikimedia Commons
From Wikipedia, the free encyclopedia

Recursive_enumeration_of_all_halting_Turing_machines.gif (683 × 371 pixels, file size: 16 KB, MIME type: image/gif)

Summary

Description
English: Shows an algorithm to enumerate the set of all Turing machines halting on a fixed input x: Simulate all Turing machines (enumerated in green on vertical axis) step by step (horizontal axis), using the shown diagonalization scheduling (red line). If a machine terminates, print its number. This way, the number of each terminating machine is eventually printed. In the example, the algorithm prints 9, 13, 4, 15, 12, 18, 6, 2, 8, 0, ...
Date
Source Own work
Author Jochen Burghardt

Licensing

I, the copyright holder of this work, hereby publish it under the following license:
w:en:Creative Commons
attribution share alike
This file is licensed under the Creative Commons Attribution-Share Alike 3.0 Unported license.
You are free:
  • to share – to copy, distribute and transmit the work
  • to remix – to adapt the work
Under the following conditions:
  • attribution – You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
  • share alike – If you remix, transform, or build upon the material, you must distribute your contributions under the same or compatible license as the original.

Captions

Add a one-line explanation of what this file represents

Items portrayed in this file

depicts

30 November 2013

15,925 byte

371 pixel

683 pixel

image/gif

cc3c86a2775b5274ba3b780379414ddae869ac1a

File history

Click on a date/time to view the file as it appeared at that time.

Date/TimeThumbnailDimensionsUserComment
current17:43, 30 November 2013Thumbnail for version as of 17:43, 30 November 2013683 × 371 (16 KB)Jochen BurghardtUser created page with UploadWizard

The following page uses this file:

Global file usage

The following other wikis use this file: