Timeline for Why can't we solve the Halting Problem by using Artificial Intelligence? [duplicate]
Current License: CC BY-SA 3.0
20 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2015 at 13:46 | vote | accept | nmomn | ||
| Mar 12, 2015 at 15:19 | review | Reopen votes | |||
| Mar 13, 2015 at 0:49 | |||||
| Mar 12, 2015 at 15:08 | comment | added | vzn | think this is excellent question; there is some research into this eg via Busy Beaver problem & other related areas, will post some answer/ links if its reopened. agreed other questions cited by R are relevant but dont think the current dup marked is actually a dup. | |
| Mar 11, 2015 at 11:45 | comment | added | Raphael | @NMO Your program does not stand a chance with that. Of course, you can check "Is the input my program up to whitespace?" but that does not help you, ultimately: there are infinitely many programs that compute the same function as yours, and any serves to prove the contradiction. You can't hope to detect all of and only these (proof by Rice's theorem), so no. Not a chance. | |
| Mar 10, 2015 at 17:34 | comment | added | Wandering Logic | Exactly! You might find this interesting: cs.stackexchange.com/a/33910/7459. | |
| Mar 10, 2015 at 17:06 | comment | added | nmomn | @WanderingLogic okay, thank you very much for your time. That means I can approach an answer in some cases through induction, which is better than none, but there is no axiom i could use to deduce a completely true answer? | |
| Mar 10, 2015 at 17:04 | comment | added | Wandering Logic | @NMO: No, the halting program shows that there are programs that a really smart person with a really big memory and sufficient (but finite) time can't determine if it is going to halt or loop infinitely. There is no mathematical way to do it correctly in all cases, it has nothing to do with how smart you are. The way to see it is by working through the proof by yourself. | |
| Mar 10, 2015 at 17:02 | comment | added | nmomn | @WanderingLogic and I also notice some people rise the question of what happens if I pass as a parameter my own program. But what If I could make my program notice If it is itself and then halt. To make it self-concious that is analysing himself. | |
| Mar 10, 2015 at 17:00 | comment | added | nmomn | @WanderingLogic but given really smart person with a really big memory and sufficient time, isn't he able to completely determine if a program is going to halt or loop infinitely? I mean by looking for repetitive structures, counters, flags, etc... If I am given a certain program and sufficient time I can decide if it is going to halt o loop. Could I make a program to check the same things I do? | |
| Mar 10, 2015 at 15:59 | comment | added | David Richerby | @NMO Your question certainly isn't insulting: don't worry. The point is that any program that uses artificial intelligence is still a program, so it still can't solve the halting problem. It's certainly possible to write a program that says either "This halts", "This doesn't halt" or "I don't know", but any such program will always say "I don't know" for infinitely many inputs. | |
| Mar 10, 2015 at 15:38 | comment | added | Wandering Logic | @Raphael: In OP's defense, he's not really asking for a computability proof, he's asking about the common logical error (made, for example, by the famous mathematical physicist Roger Penrose) that "intelligence" is a magic property stronger than an algorithm. (Penrose goes so far as to propose that consciousness must be a result of quantum gravitational effects in cellular microtubules. I kid you not.) | |
| Mar 10, 2015 at 15:02 | answer | added | Wandering Logic | timeline score: 18 | |
| Mar 10, 2015 at 15:00 | comment | added | Raphael | Well, the question I link to provides the proof you are looking for. If you don't understand the proofs there, you will have to do some reading because it's unlikely you'll understand (and accept) any proof. Sorry. | |
| Mar 10, 2015 at 14:58 | comment | added | nmomn | I know this problem is not computable. I am looking for someone to prove why my idea is wrong. I am a beginner trying to understand. Sorry if my question is insulting to you. | |
| Mar 10, 2015 at 14:57 | comment | added | Raphael | See also here, here, here and, most importantly, here. Oh, and here -- yes, the Halting problem is decidable on some classes of programs, which is why IDEs can detect some forms of looping. (Note how they never tell you "terminates always".) | |
| Mar 10, 2015 at 14:54 | history | edited | Raphael | CC BY-SA 3.0 |
deleted 28 characters in body
|
| Mar 10, 2015 at 14:53 | history | closed | Raphael | Duplicate of How to show that a function is not computable? How to show a language is not computably enumerable? | |
| Mar 10, 2015 at 14:52 | comment | added | Raphael | Why is this not answered by the fact that the halting problem is incomputable, which you seem to be aware of (see also our reference question)? Note that "intelligent" has no real meaning; we build algorithms, period. If they are randomized, they do not contradict the halting problem (because its model does not allow for randomness) but also can't solve it, always. | |
| Mar 10, 2015 at 14:19 | review | First posts | |||
| Mar 10, 2015 at 14:54 | |||||
| Mar 10, 2015 at 14:15 | history | asked | nmomn | CC BY-SA 3.0 |