Timeline for Can all lengths of shortest non-halting inputs of all Turing machines be limited by the Busy Beaver applied to the corresponding numbers of states?
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 7, 2018 at 11:16 | comment | added | lyrically wicked | I should have used the term “sequence” instead of a “set”: for example, the infinite sequence $\{0, 1, 1, 2, 2, 2, 3, \ldots\}$ contains all integers, but the infinite sequence $\{0, 0, 1, 0, 1, 2, 0, 1, 2, 3, \ldots\}$ contains infinitely many occurrences of any integer. They both evaluate to the same set, but the original sequences are significantly different. | |
| Apr 7, 2018 at 10:15 | comment | added | SSequence | what that means "exactly". But I assume you are talking about repetition or non-repetition of terms (after evaluation) that occur in definition of $E_2$ (in your question). So it would probably count as a further restriction of possibilities (2) and (3) in my comment just above. Also, I think that possibility(1) is also ruled out by the other answer given (but I couldn't fully understand the construction). | |
| Apr 7, 2018 at 10:12 | comment | added | SSequence | I think I have some sense of what you are trying to say w.r.t. to possibility(4). But, strictly speaking, a set doesn't contain repetitions. So, from that perspective, you can write down three mutually exclusive possibilities: (1) $E_2$ contains finitely many elements (2) $E_2$ contains an infinite number of elements but is not equal to $\mathbb{N}$ (3) $E_2$ is equal to $\mathbb{N}$. So yes, from that perspective it seems that possibility(1) doesn't occur and one of possibilities(2) and (3) should be correct. Regarding what you wrote as possibility(4), it isn't fully clear to me (cont.) | |
| Apr 7, 2018 at 8:35 | comment | added | lyrically wicked | Does "an infinite number of elements" in this answer imply an infinite number of different integers (so that Possibility 1 is false )? | |
| Apr 5, 2018 at 11:22 | history | edited | SSequence | CC BY-SA 3.0 |
added 20 characters in body
|
| Apr 5, 2018 at 10:57 | history | edited | SSequence | CC BY-SA 3.0 |
deleted 4 characters in body
|
| Apr 5, 2018 at 10:49 | history | answered | SSequence | CC BY-SA 3.0 |