# Relationship between a programming step and a math function discovered.

## Recommended Posts

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.

##### Share on other sites

~What function would you represent the 'halt' step by ?

##### Share on other sites

Ummmm, I think a step function maybe.

##### Share on other sites

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

##### Share on other sites

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 by studiot
##### Share on other sites

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.

##### Share on other sites

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.

Thanks bud

##### Share on other sites

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 by wtf

##### Share on other sites

28 minutes ago, ALine said:

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.

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.

Edited by wtf
##### Share on other sites

11 minutes ago, wtf said:

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.

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.

yes, apologies

##### Share on other sites

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

##### Share on other sites

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.

+1

Edited by studiot
##### Share on other sites

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 by wtf

## Create an account

Register a new account