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
24 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 15, 2020 at 7:27 | history | edited | CommunityBot |
Commonmark migration
|
|
| Dec 27, 2017 at 17:03 | comment | added | Thomas Benjamin | That was Hartley Rogers, Jr. Sorry for the typo. | |
| Dec 27, 2017 at 13:07 | comment | added | Thomas Benjamin | (cont.) information" (as an output for that particular input)? I ask because it would be reasonable to assume (?) that your "Magic Machine" has a Godel number and therefore be acceptable as an input for a universal Turing machine (which Burgin says is a subroutine in his Inductive Turing Machines). Would the universal Turing machine have a definable output if given your "Magic Machine's" Godel number as its input? Would it spit out "erroneous information"? Are there 'generalized Turing-type machine' representations for each level of the Arithmetical Hierarchy? | |
| Dec 27, 2017 at 12:46 | comment | added | Thomas Benjamin | @TimothyChow: At the risk of sounding stupid, a question: are the Godel numbers for the arithmetical hierarchy typed, that is, say for $\Sigma_n$, $\Pi_n$, and $\Delta_n$ for some fixed $n$, there exist functions in $\Sigma_n$, $\Pi_n$, $\Delta_n$ whose Godel numbers, if presented as inputs of functions in $\Sigma_{n-1}$, $\Pi_{n-1}$, $\Delta_{n-1}$, would (in the words of Harley Rogers Jr. -- see pg. 25 of his Theory of Recursive Functions and Effective Computability) make $f$ in $\Sigma_{n-1}$, $\Pi_{n-1}$, $\Delta_{n-1}$ either "undefined" for that input, or, "gives erroneous | |
| Oct 8, 2017 at 5:51 | comment | added | Turbo | The darpa funding page nextbigfuture.com/2012/04/super-turing-ai-gets-development.html (although this is not a formal reference it quotes Burgin). | |
| Oct 8, 2017 at 5:44 | comment | added | Turbo | @JoelDavidHamkins does this have anything to do with this en.wikipedia.org/wiki/Interactive_computation? | |
| Aug 1, 2017 at 4:55 | comment | added | Timothy Chow | Let us continue this discussion in chat. | |
| Aug 1, 2017 at 0:25 | comment | added | Turbo | @TimothyChow He also clarifies on 'limit' and also disses some of 'incompetent' comments there by stating 'In spite of some incompetent comments, inductive Turing machines have much higher computing power than inductive inference machine and limit partial recursive functions.'. | |
| Aug 1, 2017 at 0:17 | comment | added | Turbo | @TimothyChow ok have you looked at the comment here blog.computationalcomplexity.org/2007/03/…? he says the machine does not have to halt at all 'However, M can also obtain a result in a different way. Namely, when at some step of computation, the word written in the output tape stops changing, then this word is also the final result of the simplest inductive Turing machine M'. It seems your magic machine halts. right? | |
| Aug 1, 2017 at 0:04 | comment | added | Turbo | @TimothyChow I don't want to wait till i die. | |
| Jul 31, 2017 at 19:55 | comment | added | Timothy Chow | @777 : It would help if you would answer my question. Why do you say that my Magic Machine is not realizable? | |
| Jul 31, 2017 at 19:10 | comment | added | Turbo | @timothychow ok then what is the big deal about ITMs if they are just limit machines? | |
| Jul 31, 2017 at 19:04 | comment | added | Timothy Chow | @777 : Just to clarify, my Magic Machine is not an oracle. I can code it up in a few minutes in any programming language and it will run exactly as advertised. No tricks. So why do you say it is not realizable? | |
| Jul 31, 2017 at 19:03 | comment | added | Turbo | @TimothyChow no i did not say it is realizable. | |
| Jul 31, 2017 at 14:29 | comment | added | Timothy Chow | @777 : Ah, so you do think that my Magic Machine is physically realizable and solves the halting problem? Then why aren't you paying me $1 million? Forget about the inductive TM, which it seems you're unsure about. You understand my Magic Machine, and I can build it, and it solves a problem that everybody else seems to say is unsolvable. If you can't come up with the cash, I'm prepared to offer you a discount. | |
| Jul 31, 2017 at 3:36 | comment | added | Turbo | @TimothyChow yes it does solve the halting problem but then is the inductive TM some cheap trick to avoid oracles to solve the halting problem? | |
| Jul 31, 2017 at 1:00 | comment | added | Timothy Chow | @777 : Instead of constantly quoting other people, I recommend that you answer the questions yourself. Specifically, do you believe that my Magic Machine is "a physically realizable machine that solves the halting problem"? If not, why not? If anything is physically realizable, surely the Magic Machine is. And it seems to do as good a job as any inductive Turing machine at "solving the halting problem." Doesn't it? Please answer for yourself instead of quoting someone else. | |
| Jul 31, 2017 at 0:02 | comment | added | Turbo | no i won't. but i will not hae to buy medicne for headaches and when i teach something to students i will make more sense. | |
| Jul 30, 2017 at 23:31 | comment | added | Turbo | ..However, a recursive algorithm has to stop to give a result, but we cannot say that a network shuts down, then something is wrong and it gives no results. Consequently, recursive algorithms turn out to be inadequate.'. So he envisions internet as a machine which gives results without halting. | |
| Jul 30, 2017 at 23:28 | comment | added | Turbo | @timothychow here he might inductive TMs and limit TMs pdfs.semanticscholar.org/fb01/… (I am not sure though). 'Such big networks as INTERNET give another important example of a situation in which conventional algorithms are not adequate. Network functioning is organized by algorithms embodied in a multiplicity of different programs. It is generally assumed that any computer program, is a conventional, i.e., recursive algorithm.. | |
| Jul 30, 2017 at 23:24 | comment | added | Turbo | @timothychow in his book he says 'Although many still believe that only recursive algorithms exist and that only some of them are realizable, there are many situations in which people actually work with superrecursive algorithms' and continues examples of superrecursive algorithms include ITMs (books.google.com/…). | |
| Jul 30, 2017 at 23:18 | comment | added | Turbo | @timothychow is this also what you have in mind 'A simple inductive Turing machine produces its results without stopping. It is possible that in the sequence of computations after some step, the word on the output tape is not changing, while the simple inductive Turing machine continues working. This word, which is not changing is the result Thus the which is not changing, is the result. Thus, the simple inductive simple inductive Turing machine does not halt...'? idt.mdh.se/kurser/cd5560/12_11/LECTURES/pdf/…. | |
| Jul 30, 2017 at 22:55 | comment | added | Joel David Hamkins | Thanks, Timothy, this is very nice. I was trying to convey the same example in the last paragraph of my answer, but you did so much more colorfully! | |
| Jul 30, 2017 at 21:24 | history | answered | Timothy Chow | CC BY-SA 3.0 |