/sci/ - Science & Math » Thread #11298811

192KiB, 876x501, Abdul-Kalam.png

View Same Google iqdb SauceNAO

Anonymous Mon 13 Jan 16:58:37 2020 No.11298811 View Reply Original Report

Quoted By: >>11298835 >>11298855 >>11298906 >>11298957 >>11299143

can all pieces of code be abstracted to a single mathematical formula? for example, the sum of numbers from 1 to x is just a 2nd degree polynomial

Anonymous

Anonymous Mon 13 Jan 2020 17:10:41 No.11298835 Report

Quoted By: >>11298932

>>11298811
What do you consider as a mathematical formula exactly? Does f(x) = 1 is x is prime and f(x) = 0 if x is composite, where x is a natural number, count as such a formula?

Anonymous

Anonymous Mon 13 Jan 2020 17:21:34 No.11298855 Report

Quoted By:

>>11298811

yes, very simple formulas actually. each program is a natural number.

Anonymous

Anonymous Mon 13 Jan 2020 17:24:08 No.11298865 Report

Quoted By:

https://en.wikipedia.org/wiki/G%C3%B6del_numbering_for_sequences#G%C3%B6del_numbering

Anonymous

Anonymous Mon 13 Jan 2020 17:37:05 No.11298906 Report

Quoted By: >>11298929

>>11298811
>Does f(x) = 1 is x is prime and f(x) = 0 if x is composite, where x is a natural number, count as such a formula?

that's a primitive recursive function, so indeed it does.

see https://en.wikipedia.org/wiki/G%C3%B6del%27s_%CE%B2_function

and above.

Anonymous

Anonymous Mon 13 Jan 2020 17:45:54 No.11298929 Report

Quoted By: >>11298948 >>11298955

>>11298906
In which case the question is, can a piece of code that takes an input x and produces an output y be abstracted to a primitive recursive function?

Anonymous

Anonymous Mon 13 Jan 2020 17:46:44 No.11298932 Report

Quoted By:

>>11298835
yes

Anonymous

Anonymous Mon 13 Jan 2020 17:53:59 No.11298948 Report

Quoted By: >>11298955

>>11298929
And codes that contain the rand() or time() functions?

Anonymous

Anonymous Mon 13 Jan 2020 17:57:54 No.11298955 Report

Quoted By: >>11299153

>>11298929
>>11298948

consider that the binary encoding of any program on your computer could be interpreted as an integer.

>can a piece of code that takes an input x and produces an output y be abstracted to a primitive recursive function?

not all functions are primitive recursive.

Anonymous

Anonymous Mon 13 Jan 2020 17:59:26 No.11298957 Report

Quoted By: >>11299104

>>11298811
Yes, because sets are turing-complete and therefore can represent any computer program.

Anonymous

Anonymous Mon 13 Jan 2020 18:59:27 No.11299104 Report

Quoted By: >>11299135

>>11298957

i guess it depends on your definition of a "formula".

all the software on your machine has a finite binary representation, which can be interpreted as a natural number. if you consider this or any other finite representation as a mathematical formula, then yes. that's sort of cheating though.

primitive recursive functions are probably in closer correspondence to what you'd call a "mathematical formula" though.

Anonymous

Anonymous Mon 13 Jan 2020 19:14:52 No.11299135 Report

Quoted By: >>11299155

>>11299104
Not really dude. The diophantine sets are themselves an equivalent representation of diophantine equations, the solutions thereof are diophantine sets. A diophantine equation exists that represents any program, such that such a program halts on any solution that is in the diophantine set associated with that equation. This is an iff relationship so diophantine equations are equivalent to turing programmability.

Anonymous

Anonymous Mon 13 Jan 2020 19:18:54 No.11299143 Report

Quoted By:

>>11298811
Sure just plug up letters and symbols to the numbers in whichever irrational number

Anonymous

Anonymous Mon 13 Jan 2020 19:26:43 No.11299153 Report

Quoted By:

>>11298955
> not all functions are primitive recursive.
Obviously. But the question was about functions that can be coded.

Anonymous

Anonymous Mon 13 Jan 2020 19:30:38 No.11299155 Report

Quoted By: >>11299165

>>11299135
>A diophantine equation exists that represents any program, such that such a program halts on any solution that is in the diophantine set associated with that equation.

can you link a source?

Anonymous

Anonymous Mon 13 Jan 2020 19:39:29 No.11299165 Report

Quoted By: >>11299201

>>11299155
https://sms.math.nus.edu.sg/smsmedley/Vol-18-2/Theoretical%20computers%20and%20diophantine%20equations(Alvin%20Chan,%20KJ%20Mourad).pdf

Anonymous

Anonymous Mon 13 Jan 2020 19:57:14 No.11299201 Report

Quoted By: >>11299211

>>11299165

huh, that's neat. but even though that correspondence exists, there's no way in general to get the equation from the turing machine, right? even if there was, i don't think an unsolved equation fits OP's colloquial definition of a "mathematical formula".

Anonymous

Anonymous Mon 13 Jan 2020 20:01:46 No.11299211 Report

Quoted By: >>11299280

>>11299201
>i don't think an unsolved equation fits OP's colloquial definition of a "mathematical formula".
I guess OP has to specify in that case.
>there's no way in general to get the equation from the turing machine, right?
I seem to recall you can easily construct the root set of the polynomial but I don't remember the details offhand. It's in the same bag of tricks as enumerating programs with integers but the specifics escape me.

Anonymous

Anonymous Mon 13 Jan 2020 20:28:49 No.11299280 Report

Quoted By:

>>11299211
>I seem to recall you can easily construct the root set of the polynomial but I don't remember the details offhand

looks that way. i can't find any source that describes the strategy in full though.

Capcode	All Only User Posts Only Moderator Posts Only Admin Posts Only Developer Posts
Show Posts	All Only With Images Only Without Images
Deleted Posts	All Only Deleted Posts Only Non-Deleted Posts
Ghost Posts	All Only Ghost Posts Only Non-Ghost Posts
Post Type	All Only Sticky Threads Only Opening Posts Only Reply Posts
Results	All Grouped By Threads
Order	Latest Posts First Oldest Posts First

Your latest searches