Discussion on question by J Kusin: If the universe is finite does that nullify Godel's incompleteness, halting problem, and Church-Turing thesis?

Feeds

09:37

6

Q: If the universe is finite does that nullify Godel's incompleteness, halting problem, and Church-Turing thesis?

I'm not well versed on these topics but they all seem to rely on infinity, mainly infinite recursion or infinite space of mathematics. If there is no always "next" algorithm, the halting problem goes away for example doesn't it? Is a finite universe enough to spell their doom? Related: Can a fini...

armand

dont know about Godel, but about the halting problem i think the finitude of the universe is irrelevant. What the halting theorem says is "there is no algorithm that can take any program as input and tell you if this program will give a result or run endlessly". I think here, "endlessly" is misleading you: it does not have to be infinite. Imagine a real computer running the program, it could run until someone pulls the plug, until the computer decay's after centuries or until the Sun becomes a red giant, the point is that it wont give you a result anyway, which is the object of the theorem.

J Kusin

@armand Let's say we find out the universe will end tomorrow. Don't we have to make some adjustment to the halting problem then? I feel uncomfortable that a theory would be independent of the universe.

Hypnosifl

Do you think finding out that the universe will end tomorrow would cause us to no longer believe the arithmetical proof that there is no largest prime number? I don't think most philosophers who believe there is such a thing as objective truth about mathematical questions would ground that truth in physical realizations in such a way.

armand

Then the theorem tells you "there is no algorithm that can compute if any program will give you an answer by tomorrow". I don't understand what you are worried about. The theorem already goes as far as infinite time, so it's also valid for any shorter period of time.

J Kusin

@Hypnosifl Personally I am very cautious to make any claims about reality of numbers or math beyond being useful. I do believe math can capture/describe objective structure that humans pick up through their senses. But it also produces un-physically realizeable entities like Chaitin's constant right? I can point to 2 apples but never Ω many. I think if the universe were going to end we wouldn't care about numbers beyond a certain size to some extent. I am puzzled by math sure, but not as much for the physically realizeable portions

RodolfoAP

09:37

Godel deals about the structure of mathematical axioms, and would be independent of the properties of the universe. In general, empirical facts don't affect mathematical rules.

J Kusin

@RodolfoAP how can something be part of the universe but indepedent? Isn't that what you are asking me to accept?

@armand Ok so the halting problem stays intact but becomes irrelevant because I just consult the book that tells me when the universe ends and use that to claim any program halts on such and such day. Halting problem is as useful as a drawn unicorn in that case.

RodolfoAP

@jkusin yes. Mathematical objects are not physical things, therefore, they don't exist in the universe as such (see Aristote's theory of form and matter, which would propose such approach). They exist in our minds.

armand

I really have a hard time understanding where you're at... What book do you have exactly that tells you when the world ends ? In any case, it won't help you in computing whether a program will stop with a result before that (which is what the halting problem is). I think you don't understand what the halting problem is about. May I suggest you do a bit more research about it ?

J Kusin

@armand I don't want to keep wasting people's time so feel free to duck out. Where I'm at is saying sure, a human can write down a program that would run forever if it could (I know this isn't the halting problem per se), but what if no program can run forever? Then I have to justify why my theorems make use of infinity (maybe I say because utilizing infinity helps me solve problems). So maybe my theorems with infinity give the right answer (we can't know if any program will halt before end of universe), but I am very astray from the actual ontology of the universe if it has no infinities

@armand so infinity as a notion would be wholly within the human mind. And among things in our imagination are fantastical things like unicorns. Only infinity and real numbers have more uses for our goals. That's it

armand

The problem is you're too focused on the idea of a program running forever, when the object of the halt theorem is to know if a program will give us a result. If it does not give us a result it will run until something stops it, wether it's the end of the world or being unplugged. The point is, it won't give a result. Whether infinity is real or not has no bearing on it. And the demonstration of the theorem uses a simple ad absurdum, no appeal to infinity, so I don't see where is your problem.

J Kusin

09:37

@armand "the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run forever" Yes I am focused on running forever...it's literally the first sentence of the wiki. I am saying if we knew from another source of knowledge that nothing runs forever, would that cause us to amend the bolded portion of the theorem? I guess not according to you, so now I have to figure out how that language truly maps to reality. I feel forced into mathematical fictionalism then.

armand

The wiki formulation is misleading. Leave the wiki and pick up a text book, see the theorem itself and not a summary description written for laypeople. You admited yourself that you are not versed in the details of the halting problem. I invite you to educate yourself more about it instead on focusing on Wikipedia's formulation, missing the forest for the tree. Then you would realize that, at least in the case of the halting problem, you are worrying over nothing. Wether a computer can physically run forever or not is irrelevant to the halting problem.

J Kusin

@armand Alright fair enough. I will say I've taken a compsci class and had the halting problem explained from my professor. I will take your advice thank you.

armand

I don't mean to be disrespectful but clearly there is something you missed, it can happen to anyone. To put it clearly: the theorem does not say that programs can run forever. It says that some programs will never reach a result, which is trivial because we can write one of those, and that no algorithm exists that can take any kind of program and tell us if it's a program that will reach a result.

Spike0xff

I am puzzled about an assumption of the original question. How could we know that the universe is finite in space or time? Observing finite extent today doesn't prove finiteness tomorrow, and the only way to be certain a universe has finite duration is to observe its end. I think that the question does not make sense as posed. Perhaps something beginning with "In a finite universe..." - but then it's clear you're doing mathematics, not talking about physical reality.

Transcript for

Discussion on question by J Kusin: If…