Timeline for Is there a physically realizable inductive turing machine that can solve Hilbert's $10$th problem and can it overcome Church-Turing Hypothesis?
Current License: CC BY-SA 3.0
21 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 29, 2017 at 14:44 | answer | added | Thomas Benjamin | timeline score: 3 | |
| Jul 30, 2017 at 21:24 | answer | added | Timothy Chow | timeline score: 12 | |
| Jul 29, 2017 at 19:03 | vote | accept | Turbo | ||
| Jul 29, 2017 at 19:07 | |||||
| Jul 29, 2017 at 11:01 | answer | added | Joel David Hamkins | timeline score: 14 | |
| Jul 29, 2017 at 10:28 | comment | added | Turbo | @JoelDavidHamkins added one more paper which cites an article of yours (once for quantum computing and another for contrasting with inductive machines). | |
| Jul 29, 2017 at 10:23 | history | edited | Turbo | CC BY-SA 3.0 |
added 151 characters in body
|
| Jul 29, 2017 at 3:52 | comment | added | Steven Stadnicki | (The edit history also doesn't speak well for the subject - there's been no substantial addition to the page in nearly a decade. But that's somewhat a separate matter.) | |
| Jul 29, 2017 at 3:46 | comment | added | Steven Stadnicki | If an 'inductive Turing Machine' cannot say when it has obtained its result, how does one know what the result of the computation is? (Note that there's some commentary on the talk page of the linked Wikipedia article that asks the same question, with no real resolution.) | |
| Jul 29, 2017 at 1:50 | comment | added | Turbo | @JoelDavidHamkins Thank you I will greatly appreciate your unbiased thoughtful opinion. This has been a concern to me for a while. Please note here too en.wikipedia.org/wiki/…. Many great ideas have failed and I do not know if this inductive turing machine idea is even at least remotely reasonable. | |
| Jul 29, 2017 at 1:46 | history | edited | Turbo | CC BY-SA 3.0 |
added 194 characters in body; edited title
|
| Jul 29, 2017 at 1:40 | comment | added | Joel David Hamkins | My point was that the question should be about the theoretical power of the machines---that is the interesting question here---not whether they are physically realizable. (Of course they are not equivalent to ITTMs.) I haven't yet thought enough about the inductive machines to have an answer to that part of your question. | |
| Jul 29, 2017 at 1:37 | history | edited | Turbo | CC BY-SA 3.0 |
added 133 characters in body
|
| Jul 29, 2017 at 1:32 | comment | added | Turbo | @JoelDavidHamkins so do you agree that these 'inductive machines are different from oracle turing machines" but "much more powerful than turing machines (capable of solving Hilbert's $10$th)"? Note wiki clearly states these machines are DIFFERENT from infinite time turing machines that you talk about. This is my concern. I do not understand. | |
| Jul 29, 2017 at 1:23 | comment | added | Turbo | @JoelDavidHamkins fair enough but Burgin claims inductive machines are physically realizable in every way that we all think our computers are Turing machines and so the query 'can the Hilbert 10th problem be solved by these machines?' is still valid provided if there is any reason at all to believe these machines differ from Turing machines with oracles (which are in no way realizable in sense I just mentioned). Refer comment here by Burgin blog.computationalcomplexity.org/2007/03/… starting from 'Dear Lance,'. Note DARPA funds superrecursive algorithms. | |
| Jul 29, 2017 at 1:10 | comment | added | Noah Schweber | @JoelDavidHamkins Or thermodynamics - Turing machines aren't supposed to degrade/fall apart! (And of course black hole computing is similarly rough on the hardware.) | |
| Jul 29, 2017 at 0:08 | answer | added | Joseph O'Rourke | timeline score: 10 | |
| Jul 28, 2017 at 23:47 | comment | added | Joel David Hamkins | Not to mention the further complicating issue that according to some physical theories, the physical universe has finite size, matter and energy. | |
| Jul 28, 2017 at 23:32 | comment | added | Joel David Hamkins | Computability theory is not really about what is "physically realizable." Are Turing machines themselves physically realizable? No, because once the paper tape becomes large enough, it will have to be in orbit somehow and will inevitably tear; or if it is organized compactly somehow, then it will collapse into a stellar mass or black hole from its own gravity. It seems that there will be a finite physical upper bound for the size of a Turing machine that can actually operate, and so the physically operable Turing machines do not constitute a Turing-complete model of computation. | |
| Jul 28, 2017 at 22:48 | history | edited | Turbo | CC BY-SA 3.0 |
added 230 characters in body
|
| Jul 28, 2017 at 21:38 | history | edited | Turbo | CC BY-SA 3.0 |
edited title
|
| Jul 28, 2017 at 21:33 | history | asked | Turbo | CC BY-SA 3.0 |