Piecewise Affine Function - Revision history

Int-y1: /* Formal Definition */

2026-02-12T02:47:07Z

Formal Definition

← Older revision		Revision as of 02:47, 12 February 2026
Line 5:		Line 5:
	f_1(\vec{x}) & \text{for } \vec{x} \in H_1 \\		f_1(\vec{x}) & \text{for } \vec{x} \in H_1 \\
	& \vdots \\		& \vdots \\
	f_{p-1}(\vec{x}) & \text{for } \vec{x} \in H_{p-1} \\		f_{p-1}(\vec{x}) & \text{for } \vec{x} \in H_{p-1}
	\end{cases}</math>Where each <math>f_i(\vec{x}) = A_i \vec{x} + \vec{b_i}</math> is an affine function and the <math>H_i \subset \Z^n</math> are non-overlapping "polyhedral regions" (defined below). If <math>\vec{x}</math> is not in any region <math>H_i</math>, we say that it halts on that configuration.		\end{cases}</math>Where each <math>f_i(\vec{x}) = A_i \vec{x} + \vec{b_i}</math> is an affine function and the <math>H_i \subset \Z^n</math> are non-overlapping "polyhedral regions" (defined below). If <math>\vec{x}</math> is not in any region <math>H_i</math>, we say that it halts on that configuration.

Sligocki: Link Turing complete

2025-12-17T16:59:09Z

Link Turing complete

← Older revision		Revision as of 16:59, 17 December 2025
Line 1:		Line 1:
	A '''Piecewise Affine Function (PAF)''' is a piecewise-defined function where each case is affine (and the case constraints are polyhedra). Many [[Cryptids]] are modeled by iterated PAFs, for example, [[BMO1]]. Like [[Generalized Collatz Problems]], iterated PAFs are also proven to be Turing complete. On the [[bbchallenge]] Discord, these were originally called "Linear-Inequality Affine Transformation Automata (LIATA)" before we knew about the existing name in published literature.		A '''Piecewise Affine Function (PAF)''' is a piecewise-defined function where each case is affine (and the case constraints are polyhedra). Many [[Cryptids]] are modeled by iterated PAFs, for example, [[BMO1]]. Like [[Generalized Collatz Problems]], iterated PAFs are also proven to be [[Turing complete]]. On the [[bbchallenge]] Discord, these were originally called "Linear-Inequality Affine Transformation Automata (LIATA)" before we knew about the existing name in published literature.
	== Formal Definition ==		== Formal Definition ==
	A ''n''-dimension, ''p''-region PAF is a piecewise defined partial function <math>f: \Z^n \to \Z^n</math>:<math display="block">f(\vec{x}) = \begin{cases}		A ''n''-dimension, ''p''-region PAF is a piecewise defined partial function <math>f: \Z^n \to \Z^n</math>:<math display="block">f(\vec{x}) = \begin{cases}

Sligocki: use doi tempate

2025-12-02T16:19:19Z

use doi tempate

← Older revision		Revision as of 16:19, 2 December 2025
Line 38:		Line 38:
	<references />		<references />

	* Amir M. Ben-Amram. 2015. [https://drops.dagstuhl.de/storage/00lipics/lipics-vol020-stacs2013/LIPIcs.STACS.2013.514/LIPIcs.STACS.2013.514.pdf Mortality of iterated piecewise affine functions over the integers: Decidability and complexity]. ''Computability''. 2015;4(1):19-56. ~~[https://doi.org/10.3233/COM-150032~~ doi:10.3233/COM-150032]		* Amir M. Ben-Amram. 2015. [https://drops.dagstuhl.de/storage/00lipics/lipics-vol020-stacs2013/LIPIcs.STACS.2013.514/LIPIcs.STACS.2013.514.pdf Mortality of iterated piecewise affine functions over the integers: Decidability and complexity]. ''Computability''. 2015;4(1):19-56. {{doi\|10.3233/COM-150032}}
	* Amir M. Ben-Amram, Samir Genaim, and Abu Naser Masud. 2012. On the Termination of Integer Loops. ''ACM Transactions on Programming Languages and Systems'' 34, 4, Article 16 (December 2012), 24 pages. ~~[https://doi.org/10.1145/2400676.2400679~~ doi:10.1145/2400676.2400679]		* Amir M. Ben-Amram, Samir Genaim, and Abu Naser Masud. 2012. On the Termination of Integer Loops. ''ACM Transactions on Programming Languages and Systems'' 34, 4, Article 16 (December 2012), 24 pages. {{doi\|10.1145/2400676.2400679}}

	[[Category:Functions]]		[[Category:Functions]]

Polygon: Added category:functions

2025-10-28T19:14:25Z

Added category:functions

← Older revision		Revision as of 19:14, 28 October 2025
Line 40:		Line 40:
	* Amir M. Ben-Amram. 2015. [https://drops.dagstuhl.de/storage/00lipics/lipics-vol020-stacs2013/LIPIcs.STACS.2013.514/LIPIcs.STACS.2013.514.pdf Mortality of iterated piecewise affine functions over the integers: Decidability and complexity]. ''Computability''. 2015;4(1):19-56. [https://doi.org/10.3233/COM-150032 doi:10.3233/COM-150032]		* Amir M. Ben-Amram. 2015. [https://drops.dagstuhl.de/storage/00lipics/lipics-vol020-stacs2013/LIPIcs.STACS.2013.514/LIPIcs.STACS.2013.514.pdf Mortality of iterated piecewise affine functions over the integers: Decidability and complexity]. ''Computability''. 2015;4(1):19-56. [https://doi.org/10.3233/COM-150032 doi:10.3233/COM-150032]
	* Amir M. Ben-Amram, Samir Genaim, and Abu Naser Masud. 2012. On the Termination of Integer Loops. ''ACM Transactions on Programming Languages and Systems'' 34, 4, Article 16 (December 2012), 24 pages. [https://doi.org/10.1145/2400676.2400679 doi:10.1145/2400676.2400679]		* Amir M. Ben-Amram, Samir Genaim, and Abu Naser Masud. 2012. On the Termination of Integer Loops. ''ACM Transactions on Programming Languages and Systems'' 34, 4, Article 16 (December 2012), 24 pages. [https://doi.org/10.1145/2400676.2400679 doi:10.1145/2400676.2400679]

			[[Category:Functions]]

Sligocki: Standardize language in math formula

2025-10-28T17:51:06Z

Standardize language in math formula

← Older revision		Revision as of 17:51, 28 October 2025
Line 3:		Line 3:
	A ''n''-dimension, ''p''-region PAF is a piecewise defined partial function <math>f: \Z^n \to \Z^n</math>:<math display="block">f(\vec{x}) = \begin{cases}		A ''n''-dimension, ''p''-region PAF is a piecewise defined partial function <math>f: \Z^n \to \Z^n</math>:<math display="block">f(\vec{x}) = \begin{cases}
	f_0(\vec{x}) & \text{for } \vec{x} \in H_0 \\		f_0(\vec{x}) & \text{for } \vec{x} \in H_0 \\
	f_1(\vec{x}) & \text{if } \vec{x} \in H_1 \\		f_1(\vec{x}) & \text{for } \vec{x} \in H_1 \\
	& \vdots \\		& \vdots \\
	f_{p-1}(\vec{x}) & \text{if } \vec{x} \in H_{p-1} \\		f_{p-1}(\vec{x}) & \text{for } \vec{x} \in H_{p-1} \\
	\end{cases}</math>Where each <math>f_i(\vec{x}) = A_i \vec{x} + \vec{b_i}</math> is an affine function and the <math>H_i \subset \Z^n</math> are non-overlapping "polyhedral regions" (defined below). If <math>\vec{x}</math> is not in any region <math>H_i</math>, we say that it halts on that configuration.		\end{cases}</math>Where each <math>f_i(\vec{x}) = A_i \vec{x} + \vec{b_i}</math> is an affine function and the <math>H_i \subset \Z^n</math> are non-overlapping "polyhedral regions" (defined below). If <math>\vec{x}</math> is not in any region <math>H_i</math>, we say that it halts on that configuration.

Sligocki: /* Example */ link BMO1

2025-10-28T17:19:12Z

Example: link BMO1

← Older revision		Revision as of 17:19, 28 October 2025
Line 19:		Line 19:

	== Example ==		== Example ==
	An example of a PAF are the rules for BMO1:<math display="block">f(a,b) = \begin{cases}		An example of a PAF are the rules for [[BMO1]]:<math display="block">f(a,b) = \begin{cases}
	(a-b, 4b+2) & \text{if } a > b \\		(a-b, 4b+2) & \text{if } a > b \\
	(2a+1, b-a) & \text{if } a < b		(2a+1, b-a) & \text{if } a < b

Sligocki: /* Turing Complete */ Add note about turing completeness and the intuition but not rigor connecting that to BMO1, etc.

2025-10-28T16:35:05Z

Turing Complete: Add note about turing completeness and the intuition but not rigor connecting that to BMO1, etc.

← Older revision		Revision as of 16:35, 28 October 2025
Line 30:		Line 30:

	Independently, similar results were proven on the bbchallenge Discord in 2025 (all by reduction to Minsky machines): @Bard proved that 3-dim PAF are Turing complete: [https://discord.com/channels/960643023006490684/1239205785913790465/1420457986564030641 Discord link], @star proved that 2-dim PAF are Turing complete: [https://discord.com/channels/960643023006490684/1239205785913790465/1421271424588451915 Discord link] and Shawn Ligocki wrote up a proof sketch that 2-region PAF are Turing complete: [https://discord.com/channels/960643023006490684/1239205785913790465/1422772752980639866 Discord link].		Independently, similar results were proven on the bbchallenge Discord in 2025 (all by reduction to Minsky machines): @Bard proved that 3-dim PAF are Turing complete: [https://discord.com/channels/960643023006490684/1239205785913790465/1420457986564030641 Discord link], @star proved that 2-dim PAF are Turing complete: [https://discord.com/channels/960643023006490684/1239205785913790465/1421271424588451915 Discord link] and Shawn Ligocki wrote up a proof sketch that 2-region PAF are Turing complete: [https://discord.com/channels/960643023006490684/1239205785913790465/1422772752980639866 Discord link].

			In other words, we know that there exists a Universal PAF (which can simulate all TMs ... and thus all other PAFs) with 2-dimensions and some unspecified number of regions and another with 2-regions and an unspecified number of dimensions. Similar to [[Universal Turing Machine\|Universal Turing Machines]], we could explore the "pareto frontier" of minimal Universal PAFs by calculating exact values for the number of regions/dimensions in those specific constructions and searching for minimal values here and for more minimal sizes with 3+ dimensions and 3+ regions.

			Note: the fact that PAF in general are Turing complete does not prove anything about specific PAF problems. For example, although 2-dim PAF (and 2-region PAF) are known to be Turing complete it is not known if 2-dim, 2-region PAF are. And even if it were known that 2-dim, 2-region PAF are Turing complete, it does not mean that the BMO1 PAF specifically is. And even if the BMO1 PAF specifically was known to be Turing complete, it does not mean that the specific trajectory followed by BMO1 is undecidable. In other words, there is really no hope of using the fact that PAF are Turing complete to prove anything rigorously about a specific example (like BMO1). Instead, the proofs that PAF in general are Turing complete simply provides some intuition for why PAFs in general are probably challenging problems to solve. This is similar to how the proof that Generalized Collatz Problems are Turing complete provides some intuition for why Generalized Collatz Problems in general are probably challenging problems to solve.

	== References ==		== References ==

Sligocki: Add reference to 2-region proof and update reference style to allow specifying the sections where the proofs come from.

2025-10-28T16:17:10Z

Add reference to 2-region proof and update reference style to allow specifying the sections where the proofs come from.

← Older revision		Revision as of 16:17, 28 October 2025
Line 27:		Line 27:

	== Turing Complete ==		== Turing Complete ==
	PAF are Turing complete. This has been proven by implementing Generalized Collatz Problems and Minsky machines as iterated PAF problems: Amir M. Ben-Amram proved in 2015 that 2-dimensional PAF are Turing complete by implementing arbitrary GCP<ref>~~Amir M.~~ Ben-Amram. [https://drops.dagstuhl.de/storage/00lipics/lipics-vol020-stacs2013/LIPIcs.STACS.2013.514/LIPIcs.STACS.2013.514.pdf Mortality of iterated piecewise affine functions over the integers: Decidability and complexity]. ''Computability''. 2015~~;4(1):19-56~~. ~~[https~~:~~//doi.org/10.3233/COM-150032 doi:10.3233/COM-150032]~~</ref> and also that 2-region PAF are Turing complete.		PAF are Turing complete. This has been proven by implementing Generalized Collatz Problems and Minsky machines as iterated PAF problems: Amir M. Ben-Amram proved in 2015 that 2-dimensional PAF are Turing complete by implementing arbitrary GCP<ref>Ben-Amram 2015. Section 2: Undecidability in Two Dimensions</ref> and also that 2-region PAF are Turing complete by implementing arbitrary Minsky machines.<ref>Ben-Amram, Genaim, Masud 2012. Section 5: Loops with Two Linear Pieces</ref>

	Independently, similar results were proven on the bbchallenge Discord in 2025: @Bard proved that 3-dim PAF are Turing complete: [https://discord.com/channels/960643023006490684/1239205785913790465/1420457986564030641 Discord link], @star proved that 2-dim PAF are Turing complete: [https://discord.com/channels/960643023006490684/1239205785913790465/1421271424588451915 Discord link] and Shawn Ligocki wrote up a proof sketch that 2-region PAF are Turing complete: [https://discord.com/channels/960643023006490684/1239205785913790465/1422772752980639866 Discord link].		Independently, similar results were proven on the bbchallenge Discord in 2025 (all by reduction to Minsky machines): @Bard proved that 3-dim PAF are Turing complete: [https://discord.com/channels/960643023006490684/1239205785913790465/1420457986564030641 Discord link], @star proved that 2-dim PAF are Turing complete: [https://discord.com/channels/960643023006490684/1239205785913790465/1421271424588451915 Discord link] and Shawn Ligocki wrote up a proof sketch that 2-region PAF are Turing complete: [https://discord.com/channels/960643023006490684/1239205785913790465/1422772752980639866 Discord link].

	== References ==		== References ==
	<references />		<references />

			* Amir M. Ben-Amram. 2015. [https://drops.dagstuhl.de/storage/00lipics/lipics-vol020-stacs2013/LIPIcs.STACS.2013.514/LIPIcs.STACS.2013.514.pdf Mortality of iterated piecewise affine functions over the integers: Decidability and complexity]. ''Computability''. 2015;4(1):19-56. [https://doi.org/10.3233/COM-150032 doi:10.3233/COM-150032]
			* Amir M. Ben-Amram, Samir Genaim, and Abu Naser Masud. 2012. On the Termination of Integer Loops. ''ACM Transactions on Programming Languages and Systems'' 34, 4, Article 16 (December 2012), 24 pages. [https://doi.org/10.1145/2400676.2400679 doi:10.1145/2400676.2400679]

Sligocki: Rewrite article using PAF terminology and definitions from Ben-Amram's paper.

2025-10-28T16:03:37Z

Rewrite article using PAF terminology and definitions from Ben-Amram's paper.

← Older revision		Revision as of 16:03, 28 October 2025
Line 1:		Line 1:
	~~<blockquote>Note: This article is currently in flux as we investigate previous literature on the topic (called '''piecewise affine functions~~''' (PAF)~~) shared by @savask: https://discord.com/channels/960643023006490684/1239205785913790465/1422997913558323392</blockquote>~~'''~~Linear~~-~~Inequality Affine Transformation Automata~~ (~~LIATA~~)~~'''~~ are ~~a model for computation based upon applying affine transformations to vectors based on cases defined~~ by ~~linear inequalities. They are a generalization of the rules~~ for [[BMO1]] ~~and were~~ proven to be Turing complete.		A '''Piecewise Affine Function (PAF)''' is a piecewise-defined function where each case is affine (and the case constraints are polyhedra). Many [[Cryptids]] are modeled by iterated PAFs, for example, [[BMO1]]. Like [[Generalized Collatz Problems]], iterated PAFs are also proven to be Turing complete. On the [[bbchallenge]] Discord, these were originally called "Linear-Inequality Affine Transformation Automata (LIATA)" before we knew about the existing name in published literature.

	== Formal Definition ==		== Formal Definition ==
	A ''n''-dimension, ''k''-~~case LIATA~~ is a piecewise defined partial function <math>f: \Z^n \to \Z^n</math>:<math display="block">f(\vec{x}) = \begin{cases}		A ''n''-dimension, ''p''-region PAF is a piecewise defined partial function <math>f: \Z^n \to \Z^n</math>:<math display="block">f(\vec{x}) = \begin{cases}
	f_0(\vec{x}) & \text{if } ~~C_0(~~\vec{x}) \\		f_0(\vec{x}) & \text{for } \vec{x} \in H_0 \\
	f_1(\vec{x}) & \text{if } ~~C_1(~~\vec{x}) \\		f_1(\vec{x}) & \text{if } \vec{x} \in H_1 \\
	& \vdots \\		& \vdots \\
	f_{k-1}(\vec{x}) & \text{if } C_{~~k-1~~}(\~~vec~~{x}) \\		f_{p-1}(\vec{x}) & \text{if } \vec{x} \in H_{p-1} \\
	\end{cases}</math>Where each <math>f_i: \~~Z^n~~ \to \~~Z^n~~</math> is an affine function and ~~each~~ <math>~~C_i:~~ \Z^n ~~\to \{T,F\}~~</math> ~~is a~~ "~~linear inequality condition~~" (defined below) ~~such that for all~~ <math>\vec{x}</math> ~~at most one condition <math>C_i(\vec{x})</math> applies. If none of the conditions apply to~~ <math>~~\vec{x}~~</math>, we say that it halts on that configuration.		\end{cases}</math>Where each <math>f_i(\vec{x}) = A_i \vec{x} + \vec{b_i}</math> is an affine function and the <math>H_i \subset \Z^n</math> are non-overlapping "polyhedral regions" (defined below). If <math>\vec{x}</math> is not in any region <math>H_i</math>, we say that it halts on that configuration.

	~~Let~~ a ''~~'linear inequality term'~~'' be ~~any equation of the form~~ <math>g(\vec{x}) \~~sim~~ c</math> ~~where~~ <math>g: \Z^n \to \Z</math> is a ~~linear~~ function ~~and ~ is replaced by any~~ (in~~)equality relation (=,~~<~~,≤,~~>,≥)~~. Then let a '''linear inequality condition''' be any combination of linear inequality terms using logical AND, OR and NOT operations~~.		We define a closed, rational ''half-space'' to be a region <math>\{ \vec{x} \in \mathbb{R}^n : \vec{c} \cdot \vec{x} + d \ge 0 \}</math> for some <math>\vec{c} \in \mathbb{Q}^n</math> and <math>d \in \mathbb{Q}</math>. In other words, it is the half of n-dimensional Euclidean space on one side of a hyperplane (a subspace defined by an affine function). And let an open, rational half-space be the same thing but using strict inequality (<math>\{ \vec{x} \in \mathbb{R}^n : \vec{c} \cdot \vec{x} + d > 0 \}</math>).

	So, for example, the following are all ~~linear inequality conditions~~:		Finally, define a ''polyhedral regions'' (or simply ''polyhedron'') as the intersection of a finite number of rational half-spaces (any combination of closed and open ones). So, for example, the following are all polyhedral regions:

	* <math>a<b</math> represented formally as <math>a~~-b <~~ 0</math>		* <math>a<b</math> represented formally as <math>b-a > 0</math>
	* <math>3a \le b < 4a</math> represented formally as <math>(b-3a \ge 0) \and (4a-b > 0)</math>		* <math>3a \le b < 4a</math> represented formally as <math>(b-3a \ge 0) \and (4a-b > 0)</math>
	* <math>a = 2</math> (~~note that we allow equalities as well~~)		* <math>a = 2</math> represented formally as <math>(a - 2 \ge 0) \and (-a + 2 \ge 0)</math>

	Given a ~~LIATA~~ ''f'', we say that it halts in ''k'' steps starting from configuration <math>\vec{x}</math> iff <math>f^k(\vec{x})</math> is undefined.		Given a PAF ''f'', we say that it halts in ''k'' steps starting from configuration <math>\vec{x}</math> iff <math>f^k(\vec{x})</math> is undefined.

	== Example ==		== Example ==
	An example of a ~~LIATA~~ are the rules for BMO1:<math display="block">f(a,b) = \begin{cases}		An example of a PAF are the rules for BMO1:<math display="block">f(a,b) = \begin{cases}
	(a-b, 4b+2) & \text{if } a > b \\		(a-b, 4b+2) & \text{if } a > b \\
	(2a+1, b-a) & \text{if } a < b		(2a+1, b-a) & \text{if } a < b
	\end{cases}</math>where <math>f(n,n)</math> is undefined. BMO1 halts iff there exists k such that <math>f^k(1,2)</math> is undefined (in other words <math>f^{k-1}(1,2) = (n,n)</math> for some n).		\end{cases}</math>where <math>f(n,n)</math> is undefined. BMO1 halts iff there exists k such that <math>f^k(1,2)</math> is undefined (in other words <math>f^{k-1}(1,2) = (n,n)</math> for some n).

	This is a 2-dimension, 2-~~case LIATA~~. The 2 dimensions are the parameters ''a,b'' and the two ~~cases~~ are the <math>a<b</math> and <math>a>b</math> ~~rows~~. For each case the parameters are transformed via an affine transformation.		This is a 2-dimension, 2-region PAF. The 2 dimensions are the parameters ''a,b'' and the two regions are the half-spaces <math>a<b</math> and <math>a>b</math>. For each case the parameters are transformed via an affine transformation.

	== Turing Complete ==		== Turing Complete ==
	~~LIATA~~ are Turing complete. This has been proven by implementing Minsky machines as ~~LIATA~~:		PAF are Turing complete. This has been proven by implementing Generalized Collatz Problems and Minsky machines as iterated PAF problems: Amir M. Ben-Amram proved in 2015 that 2-dimensional PAF are Turing complete by implementing arbitrary GCP<ref>Amir M. Ben-Amram. [https://drops.dagstuhl.de/storage/00lipics/lipics-vol020-stacs2013/LIPIcs.STACS.2013.514/LIPIcs.STACS.2013.514.pdf Mortality of iterated piecewise affine functions over the integers: Decidability and complexity]. ''Computability''. 2015;4(1):19-56. [https://doi.org/10.3233/COM-150032 doi:10.3233/COM-150032]</ref> and also that 2-region PAF are Turing complete.
	* @Bard's proved that 3-dim ~~LIATA~~ are Turing complete: [https://discord.com/channels/960643023006490684/1239205785913790465/1420457986564030641 Discord link]
	* @star's proved that 2-dim ~~LIATA~~ are Turing complete: [https://discord.com/channels/960643023006490684/1239205785913790465/1421271424588451915 Discord link]		Independently, similar results were proven on the bbchallenge Discord in 2025: @Bard proved that 3-dim PAF are Turing complete: [https://discord.com/channels/960643023006490684/1239205785913790465/1420457986564030641 Discord link], @star proved that 2-dim PAF are Turing complete: [https://discord.com/channels/960643023006490684/1239205785913790465/1421271424588451915 Discord link] and Shawn Ligocki wrote up a proof sketch that 2-region PAF are Turing complete: [https://discord.com/channels/960643023006490684/1239205785913790465/1422772752980639866 Discord link].
	* In progress: Shawn Ligocki ~~is working on~~ a proof that 2-~~case LIATA~~ are Turing complete: [https://discord.com/channels/960643023006490684/1239205785913790465/1422772752980639866 Discord link]
			== References ==
			<references />

Sligocki: Sligocki moved page Linear-Inequality Affine Transformation Automata to Piecewise Affine Function: Switch to name more common in literature

2025-10-28T15:07:59Z

Sligocki moved page Linear-Inequality Affine Transformation Automata to Piecewise Affine Function: Switch to name more common in literature

← Older revision		Revision as of 15:07, 28 October 2025
(No difference)