5 ms·

You can't prevent infinite loops unless you've solved the halting problem right? They could of course just limit the run time if they really wanted to make sur

by 0x76 6y ago

You can't prevent infinite loops unless you've solved the halting problem right? They could of course just limit the run time if they really wanted to make sure scripts don't run indefinitely.

deleted 6y ago
[deleted]
pansa2 6y ago
> They could of course just limit the run time It seems as though this would be more robust than limiting the number of bytecode instructions. I wonder if that’s true and if so, why it’s not more commonly recommended.
coldtea 6y ago
>You can't prevent infinite loops unless you've solved the halting problem right? Only in general arbitrary turing complete runtimes. For restricted subsets of instructions and specific implementations of runtimes you can. E.g. one could trivially disallow "jump" control flow, and limit loops to N iterations.
- DarkWiiPlayer 6y ago
  It's more simple than that: pull the plug on the entire turing machine. Lua runs in a VM, so you can stop it from the outside, which wouldn't be possible if the code was running directly in the CPU (Without an OS underneath it, that is).
  - mikevin 6y ago
    You could argue this doesn't really count as preventing though. It's preventing a symptom instead of the underlying problem.
d33 6y ago
ePBF prevents infinite loops by restricting the language: https://lwn.net/Articles/794934/ https://lwn.net/Articles/794934/
moring 6y ago
The halting problem only says that you cannot tell if a program ever stops, i.e. takes a finite number of steps but without any a priori bounds. If you limit the number of steps to N, you can just run N steps of the program on your given input and look if it has stopped already.
- tinus_hn 6y ago
  The problem only says you can’t tell if the programs stops without actually running it. But here you’re running it anyway.
  - gwd 6y ago
    If you run it and it stops, then it stops. If you run it and it runs forever, then it runs forever. But the point is that you want to know if it's going to run forever before you hit "forever".

by 0x76 6y ago

You can't prevent infinite loops unless you've solved the halting problem right? They could of course just limit the run time if they really wanted to make sure scripts don't run indefinitely.

deleted 6y ago

[deleted]

pansa2 6y ago

> They could of course just limit the run time It seems as though this would be more robust than limiting the number of bytecode instructions. I wonder if that’s true and if so, why it’s not more commonly recommended.

coldtea 6y ago

>You can't prevent infinite loops unless you've solved the halting problem right? Only in general arbitrary turing complete runtimes. For restricted subsets of instructions and specific implementations of runtimes you can. E.g. one could trivially disallow "jump" control flow, and limit loops to N iterations.

DarkWiiPlayer 6y ago
It's more simple than that: pull the plug on the entire turing machine. Lua runs in a VM, so you can stop it from the outside, which wouldn't be possible if the code was running directly in the CPU (Without an OS underneath it, that is).
- mikevin 6y ago
  You could argue this doesn't really count as preventing though. It's preventing a symptom instead of the underlying problem.

d33 6y ago

ePBF prevents infinite loops by restricting the language: https://lwn.net/Articles/794934/ https://lwn.net/Articles/794934/

moring 6y ago

The halting problem only says that you cannot tell if a program ever stops, i.e. takes a finite number of steps but without any a priori bounds. If you limit the number of steps to N, you can just run N steps of the program on your given input and look if it has stopped already.

tinus_hn 6y ago
The problem only says you can’t tell if the programs stops without actually running it. But here you’re running it anyway.
- gwd 6y ago
  If you run it and it stops, then it stops. If you run it and it runs forever, then it runs forever. But the point is that you want to know if it's going to run forever before you hit "forever".