3 ms·
> So no, he never defines "halting", he just talks about whether or not a machine ever prints a finite number of 1's and 0's. Showing that these questions are e
by Sharlin 2y ago
> So no, he never defines "halting", he just talks about whether or not a machine ever prints a finite number of 1's and 0's. Showing that these questions are equivalent is an elementary exercise.
I think it's subtler than that. Circular programs in Turing's language are those that return to some exact earlier state and thus go into an infinite loop. So circular programs by definition do not halt. But circle-free programs can either halt or not halt!
- lisper 2y ago> Circular programs in Turing's language are those that return to some exact earlier state No, they aren't. They are programs that print a finite number of "symbols of the first kind" i.e. 0s and 1s. They can print an infinite number of other symbols. You might want to check out this branch of the discussion: https://news.ycombinator.com/item?id=40855382 https://news.ycombinator.com/item?id=40855382