User:IssaRice/Computability and logic/Decrement command in loop programs - Revision history

IssaRice: IssaRice moved page User:IssaRice/Decrement command in loop programs to User:IssaRice/Computability and logic/Decrement command in loop programs

2018-12-18T06:24:05Z

IssaRice moved page User:IssaRice/Decrement command in loop programs to User:IssaRice/Computability and logic/Decrement command in loop programs

← Older revision	Revision as of 06:24, 18 December 2018
(No difference)

IssaRice at 07:15, 16 September 2018

2018-09-16T07:15:37Z

← Older revision		Revision as of 07:15, 16 September 2018
Line 51:		Line 51:
	Python code:		Python code:

	<pre>def at_least_one(x):		<pre>def at_least_one(x):
	result = 0		result = 0
	for _ in range(x):		for _ in range(x):
	result = 1		result = 1
	return result		return result

IssaRice at 07:09, 16 September 2018

2018-09-16T07:09:01Z

@@ Line 47: / Line 47: @@
 loop X₃
+     B
-endloop X₃
+endloop X₃</pre>

IssaRice at 06:57, 16 September 2018

2018-09-16T06:57:49Z

← Older revision		Revision as of 06:57, 16 September 2018
Line 46:		Line 46:
	endloop X₂		endloop X₂
	loop X₃		loop X₃
	b		B
	endloop X₃		endloop X₃

IssaRice at 06:57, 16 September 2018

2018-09-16T06:57:23Z

← Older revision		Revision as of 06:57, 16 September 2018
Line 30:		Line 30:

	If the input is at least 1, the program enters the loop, setting <math>X_0</math> to one each time, resulting in 1 as the final output. If the input is 0, the loop is skipped ("loop zero times") and we return the default value of 0.		If the input is at least 1, the program enters the loop, setting <math>X_0</math> to one each time, resulting in 1 as the final output. If the input is 0, the loop is skipped ("loop zero times") and we return the default value of 0.

			Now we need to figure out how to write a general conditional program like:

			<pre>if condition:
			A
			else:
			B</pre>

			We can do this as follows:

			<pre>X₂ ← χ(condition)
			X₃ ← χ(¬condition)
			loop X₂
			A
			endloop X₂
			loop X₃
			b
			endloop X₃

IssaRice at 06:53, 16 September 2018

2018-09-16T06:53:02Z

← Older revision		Revision as of 06:53, 16 September 2018
Line 28:		Line 28:
	X₀ ← 1		X₀ ← 1
	endloop X₁</pre>		endloop X₁</pre>

			If the input is at least 1, the program enters the loop, setting <math>X_0</math> to one each time, resulting in 1 as the final output. If the input is 0, the loop is skipped ("loop zero times") and we return the default value of 0.

IssaRice at 06:51, 16 September 2018

2018-09-16T06:51:16Z

← Older revision		Revision as of 06:51, 16 September 2018
Line 16:		Line 16:
	I have noticed that I can implement a decrement program given if-else conditionals, as follows:		I have noticed that I can implement a decrement program given if-else conditionals, as follows:

	<pre>loop ~~X_1~~		<pre>loop X₁
	if counter != 0		if counter != 0
	~~X_0 <- X_0~~ + 1		X₀ ← X₀ + 1
	endif		endif
	counter ~~<-~~ counter + 1		counter ← counter + 1
	endloop ~~X_1~~</pre>		endloop X₁</pre>

			<math>n \ne 0 \iff n\geq 1</math>, so we just need a program that checks if the input is at least 1:

			<pre>loop X₁
			X₀ ← 1
			endloop X₁</pre>

IssaRice: Created page with "(started typing this up as a question for math SE, but I think I got it) Herbert Enderton’s ''Computability Theory: An Introduction to Recursion Theory'' defines a loop pro..."

2018-09-16T06:47:51Z

Created page with "(started typing this up as a question for math SE, but I think I got it) Herbert Enderton’s ''Computability Theory: An Introduction to Recursion Theory'' defines a loop pro..."

New page

(started typing this up as a question for math SE, but I think I got it)

Herbert Enderton’s ''Computability Theory: An Introduction to Recursion Theory'' defines a loop program as one made up of the following commands:

# The clear command <math display="inline">X_n \leftarrow 0</math> that sets the value of the variable <math display="inline">X_n</math> to zero.
# The increment command <math display="inline">X_n \leftarrow X_n + 1</math> that increases the value of <math display="inline">X_n</math> by one.
# The copy command <math display="inline">X_n \leftarrow X_m</math> that sets the value of <math display="inline">X_n</math> to that of <math display="inline">X_m</math> and leaves the value of <math display="inline">X_m</math> unchanged.
# The loop command <math display="inline">\text{loop}\ X_n; \mathcal P; \text{endloop}\ X_n</math> that takes a program <math display="inline">\mathcal P</math> and executes it <math display="inline">X_n</math> times. Here the value of <math display="inline">X_n</math> may be changed inside the loop, but this will not affect the number of times <math display="inline">\mathcal P</math> is executed. (This ensures the overall program always terminates, assuming <math display="inline">\mathcal P</math> does.)

The output of a program is always stored in <math display="inline">X_0</math>. A function <math display="inline">f\colon \mathbb N^k \to \mathbb N</math> is loop-computable if there is a loop program such that for every <math display="inline">x \in \mathbb N^k</math> the program started with <math display="inline">(X_1,\ldots,X_k) = x</math> (and zero in all the other variables) halts with <math display="inline">f(x)</math> in <math display="inline">X_0</math>.

The book then states (without proof, as far as I can tell) that a function taking values in <math display="inline">\mathbb N</math> is loop-computable if and only if it is primitive recursive.

I am confused that the above definition of a loop program does not have a decrement command. When I look at [https://en.wikipedia.org/wiki/LOOP_(programming_language)#Syntax other definitions] I see that they have a decrement command.

I have noticed that I can implement a decrement program given if-else conditionals, as follows:

<pre>loop X_1
if counter != 0
X_0 <- X_0 + 1
endif
counter <- counter + 1
endloop X_1</pre>