ALine Posted February 16, 2023 Posted February 16, 2023 A step in programming is a function in mathematics. Proof: A function is a relationship between two sets. A set can be represented as being a list or tuple of programs. A function is just a transition between programs. Therefore a step is a function. [g] 1 minute ago, ALine said: A step in programming is a function in mathematics. Proof: A function is a relationship between two sets. A set can be represented as being a list or tuple of programs. A function is just a transition between programs. Therefore a step is a function. [g] This viewpoint is from the perspective of both the philosophy of both mathematics and computer science.
studiot Posted February 16, 2023 Posted February 16, 2023 ~What function would you represent the 'halt' step by ?
Ghideon Posted February 16, 2023 Posted February 16, 2023 5 hours ago, ALine said: A step in programming is a function in mathematics. Proof: A function is a relationship between two sets. A set can be represented as being a list or tuple of programs. A function is just a transition between programs. Therefore a step is a function. I'm not sure I follow the idea, maybe you can you define "step"? On a low level (interactions for a CPU) @studiot's halt* example could mean that the CPU will wait for an external interrupt. Are these signals part of your steps? *) I use HLT (x86) here
studiot Posted February 16, 2023 Posted February 16, 2023 (edited) 5 hours ago, ALine said: Ummmm, I think a step function maybe. 3 minutes ago, Ghideon said: I'm not sure I follow the idea, maybe you can you define "step"? On a low level (interactions for a CPU) @studiot's halt* example could mean that the CPU will wait for an external interrupt. Are these signals part of your steps? *) I use HLT (x86) here I really don't know the answer to this but I was thinking that you need to distinguish between a 'do nothing' instruction and a halt instruction which is not the same thing. I would interpret a do nothing instruction as equivalent to the zero function in your terms, which surely would make it the same as Ghideon's wait instruction. Edited February 16, 2023 by studiot 1
ALine Posted February 16, 2023 Author Posted February 16, 2023 5 minutes ago, Ghideon said: I'm not sure I follow the idea, maybe you can you define "step"? Step meaning a programs execution through means of pointer reference value shifting.
studiot Posted February 16, 2023 Posted February 16, 2023 27 minutes ago, ALine said: Step meaning a programs execution through means of pointer reference value shifting. Probably best to discuss this in terms of turing machines. Here is a simulator. https://morphett.info/turing/turing.html
wtf Posted February 16, 2023 Posted February 16, 2023 (edited) 9 hours ago, ALine said: A set can be represented as being a list or tuple of programs. I'm not sure what you mean. There are uncountably many sets of natural numbers, but only countably many Turing machines. So most (in the sense of all but countably many) sets of natural numbers can not be described by programs. Can you justify your claim or put it into context? To me it seems manifestly false. Edited February 16, 2023 by wtf
ALine Posted February 17, 2023 Author Posted February 17, 2023 Can you provide an explanation to your Turing machine statement please.
wtf Posted February 17, 2023 Posted February 17, 2023 (edited) 28 minutes ago, ALine said: Can you provide an explanation to your Turing machine statement please. Was this for me? A TM program is a finite sequence of symbols taken from an at most countably infinite alphabet. There are therefore at most countably many TM programs of length 1, countably many of length 2, countably many of length 3, and so forth. The countable union of countably many sets is countable. Therefore there are at most a countable infinity of TMs. And for TMs you can substitute programs in any Turing-complete language: FORTRAN, COBOL, Python, C++, or whatever. Since there are uncountably many sets of natural numbers (per Cantor), there must necessarily be sets of natural numbers whose members can NOT be generated by any computer program. That contradicts your claim, to the extent that I can interpret it. https://en.wikipedia.org/wiki/Turing_machine This does not, by the way, contradict your thesis. Your premises are wrong but your conclusion is right! A step in a computer program is a transition from one state of the computer's hardware to some other state. Practical computers -- real-life digital computers implemented physically -- are finite state machines. They make a succession of transitions from one state to another, and those transitions can be taken to be mathematical functions. https://en.wikipedia.org/wiki/Finite-state_machine Edited February 17, 2023 by wtf
ALine Posted February 17, 2023 Author Posted February 17, 2023 11 minutes ago, wtf said: Was this for me? A TM program is a finite sequence of symbols taken from an at most countably infinite alphabet. There are therefore at most countably many TM programs of length 1, countably many of length 2, countably many of length 3, and so forth. The countable union of countably many sets is countable. Therefore there are at most a countable infinity of TMs. And for TMs you can substitute programs in any Turing-complete language: FORTRAN, COBOL, Python, C++, or whatever. Since there are uncountably many sets of natural numbers (per Cantor), there must necessarily be sets of natural numbers whose members can NOT be generated by any computer program. That contradicts your claim, to the extent that I can interpret it. https://en.wikipedia.org/wiki/Turing_machine This does not, by the way, contradict your thesis. Your premises are wrong but your conclusion is right! A step in a computer program is a transition from one state of the computer's hardware to some other state. Practical computers -- real-life digital computers implemented physically -- are finite state machines. They make a succession of transformations from one state to another, and those transitions can be taken to be mathematical functions. https://en.wikipedia.org/wiki/Finite-state_machine yes, apologies
Ghideon Posted February 18, 2023 Posted February 18, 2023 On 2/16/2023 at 8:54 PM, studiot said: really don't know the answer to this but I was thinking that you need to distinguish between a 'do nothing' instruction and a halt instruction which is not the same thing. I would interpret a do nothing instruction as equivalent to the zero function in your terms, which surely would make it the same as Ghideon's wait instruction. Thanks for the reply. I think your 'halt' is an excellent way to show what I think of but I lack the mathematic knowledge to express, +1. My reasoning: The outcome when step-by-step instructions is running in a CPU could as far as I know be expressed mathematically using boolean algebra and circuit logics. This includes the 'Null' or 'NOP'* instruction. But an instruction that requires an external interrupt does not necessary have any upper limit for how long it takes for the interrupt to occur. When the time is unbounded a "step" seems different from a mathematical perspective. I think my question is related to this statement: On 2/17/2023 at 1:29 AM, wtf said: They make a succession of transitions from one state to another, and those transitions can be taken to be mathematical functions. I'm curious what kind of mathematical functions are required and if/how that depends on the types of instructions and level of abstraction (CPU, Machine code, higher level) and if these functions are what OP described. *) No operation 1
studiot Posted February 18, 2023 Posted February 18, 2023 (edited) 12 minutes ago, Ghideon said: Thanks for the reply. I think your 'halt' is an excellent way to show what I think of but I lack the mathematic knowledge to express, +1. My reasoning: The outcome when step-by-step instructions is running in a CPU could as far as I know be expressed mathematically using boolean algebra and circuit logics. This includes the 'Null' or 'NOP'* instruction. But an instruction that requires an external interrupt does not necessary have any upper limit for how long it takes for the interrupt to occur. When the time is unbounded a "step" seems different from a mathematical perspective. I think my question is related to this statement: Yes, you are right about a no-operation, which also applies to Turing mschines. The point about a halt instruction is that as far as I know it is not Turing, but required in some older programming languages. I always used to smile at having to write Stop End Finish I'm pretty sure that was some early Fortran, not Cobol. Your point about interrupts is also interesting. +1 Edited February 18, 2023 by studiot
wtf Posted February 18, 2023 Posted February 18, 2023 (edited) 7 hours ago, Ghideon said: I'm curious what kind of mathematical functions are required and if/how that depends on the types of instructions and level of abstraction (CPU, Machine code, higher level) and if these functions are what OP described. My understanding is that these are just abstract mathematical functions. If you are in state X and an instruction puts you into state Y, that's a function, called the state transition function. They're not polynomials or exponentials or any familiar type of function. They're functions in the formal sense. Input state in, output state out. In https://en.wikipedia.org/wiki/Finite-state_machine, see the section marked Mathematical Model. Edited February 18, 2023 by wtf 1
Recommended Posts
Create an account or sign in to comment
You need to be a member in order to leave a comment
Create an account
Sign up for a new account in our community. It's easy!
Register a new accountSign in
Already have an account? Sign in here.
Sign In Now