Timeline for Is there a connection between the halting problem and thermodynamic entropy?
Current License: CC BY-SA 3.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 25, 2014 at 19:19 | comment | added | Gilles 'SO- stop being evil' | Sure, but the fact that we consider Turing machines to be interesting objects may have something to do with physics. | |
| May 25, 2014 at 1:07 | comment | added | Nikos M. | The extreme general nature of both constructs TM and CE (eg TM can simulate and compute every computable function/process and CE can be used as model of extremely many physical systems and processes) may in fact imply that this connection (maybe by a clever arrangement) is easier than initally thought, on the other hand it can be just wrong, although i dont think so | |
| May 24, 2014 at 23:23 | comment | added | David Richerby | @vzn We use the word "time" for the number of steps the machine has executed and "space" for the number of tape cells it has used but those words were chosen to appeal to our physical intuition as physical beings. But "time" is just an index into a sequence of configarations and space is just an index into a sequence of symbols. For example, consider a Turing machine where the head just whizzes off to the right. It uses infinite "time" and infinite "space" but you can figure that out in a finite amount of real time and real space | |
| May 24, 2014 at 21:15 | comment | added | vzn | +1, its a fair pov that many in CS would agree with. however note a TM is a machine and has semi-physical concepts associated with it such as time and space etcetera.... | |
| May 24, 2014 at 16:13 | comment | added | Nikos M. | maybe this link will provide further understanding of the concepts, history and interplay between information/computation/mathematics/physics etc.. | |
| May 24, 2014 at 15:11 | comment | added | Nikos M. | additionally i do have some (vague at this point) ideas about how this connection may come about, eg. maybe having a cascade of a TM with CE which one would violate the Halting Theorem, the other would violate the 2nd Law of TD, or other variations thereof, but of course someone might have even better ones | |
| May 24, 2014 at 15:05 | comment | added | Nikos M. | you have a point there, i can give many epistemological reasons why this is very plausible (eg the mathematics we do depend on the world we live, a-la Einstein), but i want sth beyond that, if i had a ready answer i would probably publish a paper :) | |
| May 24, 2014 at 14:54 | comment | added | David Richerby | You'd have to give more detail: as I said, I'm not a physicist. But I don't see how physical laws can have any impact on a construct that exists independently of physical reality. | |
| May 24, 2014 at 14:28 | comment | added | Nikos M. | 2nd Law Impossibility results have much in common to (mathematical) logic problems and circularities, maybe a connection there? | |
| May 24, 2014 at 14:14 | history | answered | David Richerby | CC BY-SA 3.0 |