4 ms·

> people are not proper Turing machines. They have limited storage and limited running time. In this sense, people aren't even proper regex machines. They have

> people are not proper Turing machines. They have limited storage and limited running time. In this sense, people aren't even proper regex machines. They have limited running time. But do you really believe the brain has less computational capacity than a regex machine? > I think the conventional view is that free will is the requirement for both good and bad actions, not that free actions are by definition good. What free will means is basically the core problem of moral philosophy, and different positions take different formulations of it. Consequentialists usually try to say that both bad and good actions are free (critics say consequentialists have absolutely zero freedom). Kantians say a free action following the categorical imperative is a good action. What I'm doing in this essay, though that's not the point of this particular essay, is showing a bijection between the categorical imperative and the halting problem.

duckerude 8y ago
If by regex machine you mean a deterministic finite state machine, then any particular DFSM has bounded memory use (based on the number of states) and bounded running time (based on the length of the input string). If they're simple enough, they can be simulated by a brain, so a brain has more computational capacity. If you can make them as complex as you want, then they can match (and exceed) the computational capacity of the brain, just by incorporating all states a brain can have and pre-computing the transitions. For practical purposes it's almost always best to treat brains (and other computers, for that matter) as Turing-complete, but I think that strictly speaking they're closer to DFSMs. But the point is that almost all predictions about people's decisions involve time bounds. When there's a time bound, those decisions become computable. "Will this program return 1" cannot be solved in general, but "Will this program return 1 within the next hour" can be.
- jeromebaek 8y ago
  > any particular DFSM has bounded memory use (based on the number of states) and bounded running time (based on the length of the input string). This is wrong. This DFSM does not halt: node with arrow pointing back to the node on empty input.
  - duckerude 8y ago
    That's not a DFSM. DFSMs can't have ε-transitions. You need at least an ε-NFA for that. I think you also need to have at least one transition for every symbol in the alphabet from every state for it to be a valid ε-NFA, and then it can be reduced to a DFSM, giving it a bounded running time.
    - jeromebaek 8y ago
      You are correct, thank you for pointing it out. But my point still stands because there exists a bijection between DFAs and NFAs.
      - duckerude 8y ago
        Any NFA can be reduced to a DFA (potentially at the cost of exponential blowup), and any DFA is also a NFA. That's not really a bijection, but it's true that they're equivalent. DFAs can run in bounded time, because every symbol takes exactly one step to be processed, and there is only one way to process a string. That also means NFAs can run in bounded time, by reducing them to DFAs first, but that's not a very satisfying explanation. A NFA rejects a string if it can not end in an accepting state. It's not intuitively straightforward to see whether that's the case, but it can be done in bounded time by exhaustively checking possible paths (which is possible with a finite number of states and a finite input string). You can't always perform that trick with Turing machines, because they can have infinitely many reachable states.

duckerude 8y ago

If by regex machine you mean a deterministic finite state machine, then any particular DFSM has bounded memory use (based on the number of states) and bounded running time (based on the length of the input string). If they're simple enough, they can be simulated by a brain, so a brain has more computational capacity. If you can make them as complex as you want, then they can match (and exceed) the computational capacity of the brain, just by incorporating all states a brain can have and pre-computing the transitions. For practical purposes it's almost always best to treat brains (and other computers, for that matter) as Turing-complete, but I think that strictly speaking they're closer to DFSMs. But the point is that almost all predictions about people's decisions involve time bounds. When there's a time bound, those decisions become computable. "Will this program return 1" cannot be solved in general, but "Will this program return 1 within the next hour" can be.

jeromebaek 8y ago
> any particular DFSM has bounded memory use (based on the number of states) and bounded running time (based on the length of the input string). This is wrong. This DFSM does not halt: node with arrow pointing back to the node on empty input.
- duckerude 8y ago
  That's not a DFSM. DFSMs can't have ε-transitions. You need at least an ε-NFA for that. I think you also need to have at least one transition for every symbol in the alphabet from every state for it to be a valid ε-NFA, and then it can be reduced to a DFSM, giving it a bounded running time.
  - jeromebaek 8y ago
    You are correct, thank you for pointing it out. But my point still stands because there exists a bijection between DFAs and NFAs.
    - duckerude 8y ago
      Any NFA can be reduced to a DFA (potentially at the cost of exponential blowup), and any DFA is also a NFA. That's not really a bijection, but it's true that they're equivalent. DFAs can run in bounded time, because every symbol takes exactly one step to be processed, and there is only one way to process a string. That also means NFAs can run in bounded time, by reducing them to DFAs first, but that's not a very satisfying explanation. A NFA rejects a string if it can not end in an accepting state. It's not intuitively straightforward to see whether that's the case, but it can be done in bounded time by exhaustively checking possible paths (which is possible with a finite number of states and a finite input string). You can't always perform that trick with Turing machines, because they can have infinitely many reachable states.