91–100 of 116 posts
Earlier quoted context omitted.
There is 1 general way to show any given program halts. Run it on each equivalency class of input and wait! This just might take forever.
That is not a determinable way though, since when a program enters a 'loop'ing state, it's unclear if it's going to halt or not.
Earlier quoted context omitted.
The key is the assumption that the machine is non-circular. So there must be a state in which it prints its last symbol (can we agree to drop the "of the first kind" qualification?). After that, it never prints another symbol, so you can just replace whatever it does after that with a halting state. But I see the problem with this now that I've written it out. The future behavior of the machine also depends on the st…
Chaitin has pointed out an important difference between such questions [1] : > In our approach to incompleteness, we shall ask whether or not a program produces an infinite amount of output rather than asking whether it produces any; this is equivalent to asking whether or not a diophantine equation has infinitely many solutions instead of asking whether or not it is solvable. If one asks whether or not a diophantine…
"...the term halting problem, the modern formulation of the problem, as well as the common self-referential proof of its undecidability, are all, strictly speaking, absent from Turing’s work. However, Turing does introduce the concept of an undecidable decision problem, proving that what he calls the circle-free problem is undecidable and subsequently also that what we call the symbol-printing problem, to decide if a given program will ever print a given symbol, is undecidable. This latter problem is easily seen to be computably equivalent to the halting problem and can arguably serve in diverse contexts and applications in place of the halting problem—they are easily translated to one another."
So I was basically correct, just wrong about a detail: it is the symbol-printing problem that is easily translated to the halting problem, not the circle-free problem. So I am going back to standing by my initial assessment: saying that Turing's paper was not about the halting problem because it doesn't actually use that exact phrase is like saying that the EPR paper was not about entanglement because it doesn't use that exact word.
Earlier quoted context omitted.
In general, it absolutely does. I'm not sure what you're trying to say. (1) Yes, there are classes of programs for which you can say whether it halts (2) Yes, there are programs who do not fall into those classes who can be shown to halt But the point remains... there's no 'general' way to show that any program halts. Part of the point of good PL design is to produce a language that is amenable to analysis, including…
But do we need general ways to show that any program halts? We don't write general programs In particular, our programs have a limited size and use a limited amount of memory (or else the OS will make sure they will halt..). And for this specific class of programs, the halting problem is actually decidable!
While it's true that the class of programs that terminate in time at most T is decidable for trivial reasons (just run the program for at most time T), that trivial decider is of course not gonna run in time T (but at least T+1). So if you set T=time until the heat death of the universe, you haven't gained any practical ability to solve the halting problem either.
Earlier quoted context omitted.
I would like to add that even deciding if a particular single program halts can be undecidable. At least in PA or ZFC, and I don't think there is a better math framework. There was a pretty cool Bachelor's thesis (I think? Can't recall) that that used this fact to show that busy beavers beyond some point cannot be determined. And even without any trickery, deciding single program halting can be extremely hard. For in…
It is never undecidable to determine whether a single particular program halts or not. For any single program, one of these two functions will correctly output whether it halts or not. bool always_true(TuringMachine M) { return true; } bool always_false(TuringMachine M) { return false; } It won't work for every Turing Machine, but it will work for a specific one. This is why it's not very meaningful to talk about the…
Saying "one of these functions is correct" is not a decision procedure. You actually need to decide which one of them is correct.
> This is why it's not very meaningful to talk about the decidability of particular Turing Machines
I disagree. There are particular Turing machines whose decidability is extremely meaningful. For example, there are specific Turing machines which encode mathematical problems of interest such as the Goldbach conjecture. Deciding whether they halt is equivalent to solving those mathematical problems, which is definitely meaningful.
I think you can use a Turing-like argument to argue against the existence of a finite set of moral rules that covers every situation too. The argument goes: suppose you have some set of rules. Now engineer a situation where, if the rules are followed, you cause something bad to happen. That’s similar to the step where turing says, “now create a program that asks if p halts, and if so runs an infinite loop”.
Which means, no sacred text or set of commandments could possibly cover every situation.
Earlier quoted context omitted.
> In general, it absolutely does. I'm not sure what you're trying to say. I can see that you don't so I'll try to be clearer. For any given program one might choose there is no reason in principle why a competent computing scientist can't perform a semantic analysis for every statement and then deduce from that whether it is totally or partially correct. Obviously most programs in the set of all programs are too long…
> I can see that you don't so I'll try to be clearer. For any given program one might choose there is no reason in principle why a competent computing scientist can't perform a semantic analysis for every statement and then deduce from that whether it is totally or partially correct. 'Correct'? In what sense? 'Correctness' and halting have little to do with each other. For example: def f(p): p() return 2 is 'correct'…
Confident ignorance isn’t a good look. To help you out, here you go from the wiki[1]:
Within the latter notion, partial correctness, requiring that if an answer is returned it will be correct, is distinguished from total correctness, which additionally requires that an answer is eventually returned, i.e. the algorithm terminates.
[1] https://en.m.wikipedia.org/wiki/Correctness_(computer_scienc...
Earlier quoted context omitted.
> In general, it absolutely does. I'm not sure what you're trying to say. I can see that you don't so I'll try to be clearer. For any given program one might choose there is no reason in principle why a competent computing scientist can't perform a semantic analysis for every statement and then deduce from that whether it is totally or partially correct. Obviously most programs in the set of all programs are too long…
I'm sure you know this, but even very simple/short programs can have complex behaviours that put them out of reach of computer scientists with present-day knowledge. For example, short programs can encode things like the Goldbach conjecture, the Collatz conjecture, or the Riemann Hypothesis. For example, does this program (written in Python, but translate to your computational system) halt? def isprime(n): return n >…
Like many people I had a casual go at it for Collatz. It was a humbling experience of course, but it did nothing to convince me some more capable person can’t eventually manage it.
Earlier quoted context omitted.
> I can see that you don't so I'll try to be clearer. For any given program one might choose there is no reason in principle why a competent computing scientist can't perform a semantic analysis for every statement and then deduce from that whether it is totally or partially correct. 'Correct'? In what sense? 'Correctness' and halting have little to do with each other. For example: def f(p): p() return 2 is 'correct'…
> ‘Correct'? In what sense? 'Correctness' and halting have little to do with each other. Confident ignorance isn’t a good look. To help you out, here you go from the wiki[1]: Within the latter notion, partial correctness, requiring that if an answer is returned it will be correct, is distinguished from total correctness, which additionally requires that an answer is eventually returned, i.e. the algorithm terminates.…
But regardless, it's pretty clear from your ramblings that you're not well-versed in this stuff. As for my part, I implement theorem provers and programming languages, so what do I know
Earlier quoted context omitted.
Penrose's entire thesis seems to boil down that AGI is impossible because brains use Quantum Oogly-Boogly and that since Quantum Oogly-Boogly isn't computable, no computer can do it. The Emperor's New Mind is a tour de force of a book, but its central premise feels thoroughly unconvincing, or at least poorly communicated.
It's been a long time since I've read TENM but I don't think Penrose argued that AGI was impossible, just that consciousness was not computable by a Turing machine. Presumably you could create AGI by utilising these quantum effects if it turns out that Penrose is correct and they do something. I wouldn't particularly bet on Penrose being correct but until someone figures out how consciousness actually works or proves…
Despite my flippant rejection of Penrose I very much agree. I just thought the computational approach was misguided and his colleagues did him dirty.
Earlier quoted context omitted.
It is never undecidable to determine whether a single particular program halts or not. For any single program, one of these two functions will correctly output whether it halts or not. bool always_true(TuringMachine M) { return true; } bool always_false(TuringMachine M) { return false; } It won't work for every Turing Machine, but it will work for a specific one. This is why it's not very meaningful to talk about the…
> For any single program, one of these two functions will correctly output whether it halts or not. Saying "one of these functions is correct" is not a decision procedure. You actually need to decide which one of them is correct. > This is why it's not very meaningful to talk about the decidability of particular Turing Machines I disagree. There are particular Turing machines whose decidability is extremely meaningfu…
That's precisely what a decision procedure is, it's an algorithm that takes as input the description of a Turing machine, and an input, and returns true if and only if the Turing machine halts when given the input. You are using the term "decide" as if there were some kind of agency involved, like you have to actually "choose" what is correct or incorrect, but no such agency is involved, it is a purely mechanical process.
>There are particular Turing machines whose decidability is extremely meaningful.
You are mixing up the notion of decidability with the notion of halting, and there is a subtle difference. The Turing machine that encodes the Goldbach conjecture proves the conjecture if it halts, and disproves the conjecture if it doesn't halt. That is an interesting and meaningful property of such a Turing machine. What is not meaningful or interesting is whether that particular Turing machine is decidable.
As I said, there is a subtle difference between whether a Turing machine halts or not, and whether it's decidable whether it halts or not. The former is interesting, the latter is not particularly insightful.