Timeline for Different notions of computable binary sequence
Current License: CC BY-SA 3.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 28, 2017 at 20:07 | vote | accept | grok | ||
| Nov 28, 2017 at 20:06 | vote | accept | grok | ||
| Nov 28, 2017 at 20:07 | |||||
| Nov 28, 2017 at 20:06 | vote | accept | grok | ||
| Nov 28, 2017 at 20:06 | |||||
| Nov 28, 2017 at 16:32 | comment | added | Arno | @YCor The input to that decision problem is obviously the sequence $s$. We can view this in two ways: The Polish style, where the sequence is written out on the input tape, or the Russian style, where the sequence is given by the code of a Turing machine that would write it. For natural problems, it usually makes no difference regarding decidability of questions, and this applies here. | |
| Nov 28, 2017 at 12:46 | comment | added | YCor | when you say "it's not decidable whether there is a 1 in $s$", I'm not sure what you mean. If you have in mind that the input is $s$ (an arbitrary element of $\{0,1\}^\omega$), this is not a possible input for a Turing machine: you can input an integer or an equivalent datum, e.g. a finite sequence. When you say "whether there is a 1 in $s$ at position $\ge i$", again the input can't be $s$, but let's say that the input is $i$. Then you get the characteristic function of an initial segment of $\omega$, and this is obviously a computable function. | |
| Nov 28, 2017 at 12:26 | answer | added | Arno | timeline score: 1 | |
| Nov 28, 2017 at 8:38 | comment | added | grok | Yes, you're right that my question is imprecise. I was hoping that there was a large class of Turing machines for which, at least, the above predicates are decidable -- something much larger than rational. @usul, we might write $i$ in unary, and view $s\subset\{0\}^*$, or in binary, and view $s\subset\{0,1\}^*$, the answers will definitely be different but both interest me! | |
| Nov 28, 2017 at 1:10 | comment | added | usul | Can you say more about what you mean by "strengthening"? It's a very broad question. If we view $s$ as a subset of all strings on a finite alphabet, where $s[i] = 1$ if and only if the $i$th string is in the language, then all of formal languages are relevant, e.g. regular, context-free, etc. | |
| Nov 27, 2017 at 22:20 | answer | added | Bjørn Kjos-Hanssen | timeline score: 7 | |
| Nov 27, 2017 at 21:40 | history | asked | grok | CC BY-SA 3.0 |