Loading...
Please wait, while we are loading the content...
Similar Documents
Undecidability
| Content Provider | Scilit |
|---|---|
| Author | Reiter, Edna E. Johnson, Clayton Matthew |
| Copyright Year | 2017 |
| Description | What does it mean to be undecidable? The definition will be easy: “no algorithm exists”; that is, there cannot be any Turing machine that halts on all inputs with a yes or no answer. But understanding this definition, and using it to show certain problems are undecidable, is a harder proposition. In particular, finding the first undecidable problem takes some work. The only way to prove that something does not exist will be by contradiction—for a particular problem (acceptance of a string by a Turing machine), assume that an algorithm exists, then show that this produces an impossible situation. That will mean that our assumption about the existence of the algorithm is wrong. Book Name: Encyclopedia of Computer Science and Technology |
| Related Links | https://content.taylorfrancis.com/books/download?dac=C2013-1-18440-3&isbn=9781315115894&doi=10.1201/9781315115894-78&format=pdf |
| Ending Page | 802 |
| Page Count | 7 |
| Starting Page | 796 |
| DOI | 10.1201/9781315115894-78 |
| Language | English |
| Publisher | Informa UK Limited |
| Publisher Date | 2017-10-02 |
| Access Restriction | Open |
| Subject Keyword | Book Name: Encyclopedia of Computer Science and Technology History and Philosophy of Science Wrong String Inputs Proposition Answer Impossible Undecidable Problem Harder Halts Takes |
| Content Type | Text |
| Resource Type | Chapter |
