@DavidRicherby I have not looked at that stuff in several decades, so my memory is fading a bit. So I am a bit slow in replying. Also, applying it to Turing machines is my idea (probably not original, but I have not seen it done). The difficulty is that Turing mchines are very simple devices so that the benefits of the construction are not very visible.
Let us forget a bit about my finite automata, that are somewhat shapeless, or more usefully consider them as built as TM with finite tape. They all have the same finite control, and an automaton A is said to be more defined than an automaton B if the tape of A exceeds on both sides the tape of B (this can be checked in the initial configuration).
These automata form a complete partial order with the approximation relation: any set of automata has a least upperbound which is actually defined, in the finite case as the automaton having the maximum length of tape in both direction, from all the automata in the set. But the LUB for an increasing infinite chain of automata is a TM with a tape that is infinite on at least one side. Etc ... TM with infinite tapes on both sides can be obtained by the same mechanism.
This way you get exactly all TM. Now these TM may be understood as limits for the infinitely increasing chain.
Now, to show that they behave as limits, and as continuous functions with respect to limits, I would need to introduce data domain, show that TM are continuous w.r.t. data domains (that is not too hard I think). Then I would want to consider universal TM, or at least TM taking TM as arguments, and show that everything still works fine, with the universal TM being continuous w.r.t. TM as limits of their finites approximations.
@DavidRicherby I do not know how long it would take me to write this down more or less formally, but I am pretty sure it can be done, and I would be surprised if it had not already be done somewhere. Actually, I tend to think it would be nice to teach things that way. First it would debunk this nonsense about the infinite tape. Second it would tie together formal semantics with TM, rather than leave a monopoly to lambda-calculus, sort of ghettoizing the idea.
Finally, I think it could tie in well with complexity as a measure of the kind of finite approximation you need for your TM to make it run on a given input. I find it kind of bothersome that semantics and complexity/algorithmics are distinct communities that do not seem to communicate too much, and may appear irrelevant to each other. Maybe it is no longer the case with current research, involving type theory and automatic generation of programs, as that now exceeds my competence.
Another advantage is possibly that it is a very simple introduction to semantics, that could be more accessible to some students. Well... have a good night.
We have deployed the latest Mathjax 2.5 alpha on Math.SE. As with any beta release please post an answer to this question if you find any issues. We will be monitoring this thread closely along with the authors of Mathjax to ensure this release goes smoothly.
This particular release has a new f...
@Raphael the first part of the question isn't even on-topic: “Are all Morse code strings uniquely decipherable?” isn't a question about coding theory or modeling or anything, it's just asking for a factoid about a technology. And that's all the accepted answer covers.
I'd like to edit the question to focus on the science aspects: an algorithm to list all possible messages (second part of the question), or (more interesting but not contained in the present question) how to tell whether a coding system is ambiguous for a given dictionary.
@Raphael I am afraid that is part of SE. Science has never been a voting matter. Voting is for matters of opinion, which are supposed to be unwelcome on SE. In other words, SE is inconsistent. After FIFO and LIFO, this is the third data management policy: GIGO.
This is too bad, there are interesting questions that could be asked. The point is that the question is about prefix codes, and the best you can do with at most 4 bits is 16 different codes, not 24. And I am sure there is plenty of other interesting stuff that is not evoked.
But then we all know that difficult answer bring few votes if any, while trivial one work pretty well, though unpredictably. And I know that I do not vote often on questions that are harder, because I first want to understand. All this is just built-in.
Once again, science is not, never has been a voting matter.
This is not a homework help site, this is a question and answers site. On a homework help site, “I provide a hint and let the guy do his own homework” is a valid justification for leaving hints.
But Stack Exchange is a kind of Wikipedia for non-notable questions. Answers are not there for the asker, they're for all future visitors. Answers should be useful for anyone who finds this question in a search, not just the guy whose homework is due tomorrow.
Yuval has a bad habit of posting hints as answers.
& the mods have a habit of wanting to overrule strong majority votes/ indications, not always following topvoted meta policy etc. & opinions about policy of high rep users. eg
I think that hints should be provided as answers. This isn't a site for doing people's homework, but helping them understand the ideas that will help them to do their own homework. Sometimes a hint is sufficient to achieve that goal.
One difference with TeX.SE (and correct me if I'm wrong) is t...
@DavidRicherby [Turing Machines as limits] To answer your remarks "what does your limit operation do if I try to take the limit of a sequence of automata that doesn't "converge" to an RE language?". The syntactic order that is used to define limits as LUB is such that it ensure a form of consistency between sequences of automata that will not allow not converging on a RE language.
DR, do you want to pay attn to meta or not? is it maybe just a bunch of useless archives?
as for "strong majority vote," the hot question that both mods are complaining about has over 45v. moreover R/G are specifically ignoring sentiment on a highly upvoted comment justifying the top answer as legitimate/ acceptable.
guess its just Senate/ Senators vs the House around here....
the mods complain endlessly about the site not graduating, but its not graduating apparently due to scale, and hot questions are examples of increasing scale, and mods repeatedly dislike hot questions... :\
@vzn The highly upvoted comment is completely spurious. It justifies the answer by claiming that the question says something it manifestly does not say. I genuinely do not understand how that comment has so many up-votes.
Go on, then. Explain to me what part of the question "seems to be asking whether one series of dots and dashes without spaces could be interpreted as two 'real' messages as opposed to arbitrary sequences of T and E."
The highly upvoted comment that you were lauding a moment ago.
I quoted part of it, which claims that the question "seems to be asking whether one series of dots and dashes without spaces could be interpreted as two 'real' messages as opposed to arbitrary sequences of T and E." I then asked you to explain to me how the question actually seems to do that.
> The OP seems to be asking whether one series of dots and dashes without spaces could be interpreted as two "real" messages as opposed to arbitrary sequences...
I think that hints should be provided as answers. This isn't a site for doing people's homework, but helping them understand the ideas that will help them to do their own homework. Sometimes a hint is sufficient to achieve that goal.
One difference with TeX.SE (and correct me if I'm wrong) is t...
