Skip to main content
Brent's user avatar
Brent's user avatar
Brent's user avatar
Brent
  • Member for 11 years, 7 months
  • Last seen more than 2 years ago
awarded
awarded
awarded
revised
Are there algorithms to exactly minimize NFAs which are sometimes efficient?
Fix broken source code link. Add Google Scholar search link for the paper.
Loading…
comment
Formal Description Of Data Structure For Infinite Sets Of Reals
What about algorithms on the data structure, like union and intersection and complement?
Loading…
Loading…
awarded
comment
Why, really, is the Halting Problem so important?
Your last assertion is true in general, but not for all cases. (I didn't give you a downvote)
revised
Loading…
comment
Is C actually Turing-complete?
The library doesn't give access to a PDA. It gives access to stacks. The question specifically asks about the semantics of C, and calling functions to access an unbounded stack is just as semantically valid as using a pointer to access RAM. You might as well argue that C doesn't let you implement RAM, but only gain access to it. The distinction is meaningless.
revised
Is C actually Turing-complete?
deleted 7 characters in body
Loading…
comment
Why, really, is the Halting Problem so important?
Interesting corollary to the applicability of the linked-list loop detection algorithm: If a finite-state push-down automaton never repeats then it must use a logarithmic (in time) amount of memory. At the end of eternity it will have written to an infinite amount of memory.
revised
Is C actually Turing-complete?
deleted 39 characters in body
Loading…
revised
Is C actually Turing-complete?
deleted 39 characters in body
Loading…
revised
Is C actually Turing-complete?
added 1 character in body
Loading…
comment
Is C actually Turing-complete?
This answer is actually right.
revised
Is C actually Turing-complete?
added 1 character in body
Loading…
1
2 3 4 5
7