And here I thought it was simply about a system of equations solving down to a single solution (decidable).
As opposed to having too many free variables.
What does “Undecidable” mean, anyway
21–30 of 196 posts
Re: What does “Undecidable” mean, anyway
#22I sometimes wonder if the concept of “intelligence” is going to benefit from a formal model the way “computation” benefited from Turing Machines. Are there classes of intelligence? Are there things that some classes can and cannot do? Is it a spectrum? Is the set of classes countable? Is it finite? Is there a maximum intelligence? One can dream…
Philosophers have been trying to define what it means to be conscious since forever. I think that is informally what you mean here.
If you just mean what problems can it solve, and how quickly, we already have a well developed theory of that in terms of complexity classes -https://complexityzoo.net/Complexity_Zoo
Re: What does “Undecidable” mean, anyway
#23Earlier quoted context omitted.
Do you know whether there is an algorithm which "mostly" solves the halting problem, by returning either "halts", "doesn't halt" or "don't know", while only very rarely returning "don't know" for (what we would intuitively consider) natural algorithms?
Yes. Take the one which might not halt and add an integer argument which you decrement on recursion/loop, possibly called "fuel", and return don't know when that hits zero. Then call your algorithm with a large integer for that argument and wait.
Practically speaking, if your goal is to protect system resources, which is a practical concern removed from theoretical computer science, the halting problem isn't even the right concern. It's good to know about and all, but the problem is that programs which halt can be a nuisance. You don't care about the difference between "runs for 5 days and halts" and "runs forever".
Some programs run indefinitely by design, like services. Those may be acceptable in a system, but not CPU-intensive, long-running programs.
So you in fact have to reject some programs which halt, and accept some which don't.
Re: What does “Undecidable” mean, anyway
#24Earlier quoted context omitted.
Would you have book recommendations / resources to share?
Might be hard to approach but my favorite is Pierce's "Types and Programing Languages": https://www.cis.upenn.edu/~bcpierce/tapl/ (known as TAPL). Was grateful to take a graduate level class using it in college.
TAPL is nice, and also very dense. I haven't fully read it, but my current understanding is the follow: Both the Turing Machine and the lambda calculus only describes how to act on data. They don't actually describes what the data is. So you can craft an algorithm that works well, but it can be supplied with the wrong type of data and it will goes haywire. Your only recourse is to trust the user of your algorithm.
What type does is to have a set of classes of data, then have rules between those classes. You then annotate your code with those classes (combining them if it's possible) and then your type system can verify that the relations between them hold. To the type system, your program is data.
Re: What does “Undecidable” mean, anyway
#25> I often see the halting problem misconstrued as "it's impossible to tell if a program will halt before running it." This is wrong. > The halting problem says that we cannot create an algorithm that, when applied to an arbitrary program, tells us whether the program will halt or not. Or more simply: No program can tell whether any program will halt or not.
> No program can tell whether any program will halt or not.
Might try for another wording which isn't easily misunderstood. I was going to suggest every instead of any but that supports a different misunderstanding.
Re: What does “Undecidable” mean, anyway
#26One of the biggest boost to my SWE career was studying theory of computation and programming languages theory. My major was electronic engineering, so I didn't touch those at the university. But I use some books to at least grasp the introductory knowledge. The boost was how easy it is to find the mechanism to some abstractions. And instead of being those amazing and complex tools that you have to use carefully, they…
Would you have book recommendations / resources to share?
Mertens Theory of Computation
Re: What does “Undecidable” mean, anyway
#27I sometimes wonder if the concept of “intelligence” is going to benefit from a formal model the way “computation” benefited from Turing Machines. Are there classes of intelligence? Are there things that some classes can and cannot do? Is it a spectrum? Is the set of classes countable? Is it finite? Is there a maximum intelligence? One can dream…
Philosophers have been trying to define what it means to be conscious since forever. I think that is informally what you mean here. If you just mean what problems can it solve, and how quickly, we already have a well developed theory of that in terms of complexity classes - https://complexityzoo.net/Complexity_Zoo
I think this is more about levels or classifications of intelligence.
If you've ever interacted with a very smart animal, it's easy to recognize that their reasoning abilities are on par with a human child in a very subjective and vague way. We can also say with extreme confidence that humans have wildly different levels of intelligence and intellectual ability.
The question is, how do we define what we mean by "Alice is smarter than Bob". Or more pertinently, how do we effectively compare the intelligence and ability of an AI to that of another intelligent entity?
Is ChatGPT on par with a human child? A smart dog? Crows? A college professor? PhD level?
Of course we can test specific skills. Riddles, critical thinking, that sort of thing. Problem is that the results from a PhD will be indistinguishable from the results of a child with the answer key. You can't examine the mental state of others, so there's no way to know if they've synthesized the answer themselves or are simply parroting. (This is also a problem philosophers have been thinking about for millenia)
Personally, I doubt we'll answer these questions any time soon. Unless we do actually develop a science of consciousness, we'll probably still be asking these questions in a century or two.
Re: What does “Undecidable” mean, anyway
#28Re: What does “Undecidable” mean, anyway
#29I don't know, I can't decide...
[deleted]
Re: What does “Undecidable” mean, anyway
#30Earlier quoted context omitted.
Introduction to the Theory of Computation by Michael Sipser. There's also his course based on the book on YouTube[0]. Language Implementation Patterns by Terence Parr. It avoids the theory in other books, going for a more practical approach. Then it was just trying a lot of programming paradigms like functional programming with Common Lisp and Clojure, logic programming with Prolog, array and stack programming with U…
I'd recommend codifying such axioms, rules and grammar into a domain-specific language, and then writing your logic in that DSL. It will keep things consistent and allow newcomers to quickly understand the domain, enabling them to contribute without need for deep institutional knowledge.
That's one of the foundation of Domain-Driven Design. First you try to comes up with a glossary (aka your axioms). Then you'll notice that some have relations with each other and some terms may have the same name, but refers to two different concepts (or two parts of the same whole). So now you will have your boundaries. Then you try to make a subdomain internally consistent. But you still have to communicate with the other subdomains (to enact actions and query data). These communications are equally important as each subdomain. The hope is to have something that reflects the business domain, especially the cost of changes. Something that's easy/hard to change in the business should be easy/hard to change in the code,
With OOP, this often results in verbose code, because each view of the data (which has its own rules) has its own class. With FP, because you often use more primitive data structures, it's easier to commute between subsets of data.