Timeline for Rationale behind an requirement on Turing machines
Current License: CC BY-SA 3.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 26, 2014 at 23:43 | comment | added | Jason Rute | It depends what you exactly need. Take Joel's example. For each number n, let ##n be the encoding I described above. (For example, ##100 = 11 00 00 10...) Let #n be the encoding you described (so #100 = 00100…). There is a Turning machine, which for all n, reads in the tape ##n, halts, and returns 1 if there are at most three 1s in n and 0 otherwise. The same is also true for every Turing computable function. However, as Joel said, you cannot ask for a Turning machine which reads in #n and returns 1 if there are at most three 1s in n and 0 otherwise. | |
| Aug 26, 2014 at 20:24 | comment | added | Hans-Peter Stricker | You seem to imply that one does not really need to require a blank symbol? So what is your specific answer? "In fact one does not need to require a blank symbol because there are encoding schemes that allow to neglect them?" How can this meta-mathematical statement be made totally precise? | |
| Aug 26, 2014 at 20:18 | comment | added | Per Alexandersson | Ah, nice encoding scheme! | |
| Aug 26, 2014 at 20:12 | history | edited | Jason Rute | CC BY-SA 3.0 |
added 1 character in body
|
| Aug 26, 2014 at 20:03 | history | answered | Jason Rute | CC BY-SA 3.0 |