Post History
A program may output a boolean value by using different amount of time or instructions till it returns. If a program needs to determine a boolean value, it may return in less than N second (or ins...
Answer
#3: Post edited
by
H_H
·
2023-09-19T15:23:40Z (7 months ago)
- ## A program may output a boolean value by using different amount of time or instructions till it returns.
If a program needs to determine a boolean value, it may loop for a long time when the value is `true` but exits in a short amount of time if the value is `false`, or vice versa. Alternatively a number of instructions can be used instead of time (useful when running on computers with very different performance)The difference has to be large enough to be detectable without much effort. I would suggest there is a factor of at least 32 between `true` and `false`. The difference of infinite should be allowed (if it doesn't return after N second, kill it and consider the result as `true`).
- ## A program may output a boolean value by using different amount of time or instructions till it returns.
- If a program needs to determine a boolean value, it may return in less than N second (or instructions) when the value is `false` but take longer than N + ϵ second (or instructions) when the value is `true` or vice versa.
- The difference (ϵ) has to be large enough to be detectable without much effort. I would suggest there is a factor of at least 16 between `true` and `false` (i.e. $ϵ > 15 \cdot N$) . A infinite ϵ should be allowed (if it doesn't return after N second, kill it and consider the result as `true`). The poster has to give an estimate of N.
#2: Post edited
by
H_H
·
2023-09-19T15:11:42Z (7 months ago)
## A program may output a boolean value by halting or looping forever.I am not so sure about it, since you can't detect that for arbitrary programs, but i suggest it anyway.If a program needs to determine a boolean value, it may loop forever when the value is true but exits if the value is false, or vice versa.If there is a runtime limit on the challenge, then a program that didn't exit till the time runs out is considered non-halting.
- ## A program may output a boolean value by using different amount of time or instructions till it returns.
- If a program needs to determine a boolean value, it may loop for a long time when the value is `true` but exits in a short amount of time if the value is `false`, or vice versa. Alternatively a number of instructions can be used instead of time (useful when running on computers with very different performance)
- The difference has to be large enough to be detectable without much effort. I would suggest there is a factor of at least 32 between `true` and `false`. The difference of infinite should be allowed (if it doesn't return after N second, kill it and consider the result as `true`).
#1: Initial revision
by
H_H
·
2023-09-12T13:12:16Z (8 months ago)
## A program may output a boolean value by halting or looping forever. I am not so sure about it, since you can't detect that for arbitrary programs, but i suggest it anyway. If a program needs to determine a boolean value, it may loop forever when the value is true but exits if the value is false, or vice versa. If there is a runtime limit on the challenge, then a program that didn't exit till the time runs out is considered non-halting.